1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class ilo {

	abstract class FiboIterator {
		long k = 0;

		long fk1 = 0;
		long fk2 = 0;

		long fv;

		abstract FiboIterator getNext();

		abstract long getValue();
	}

	class FiboIterator1 extends FiboIterator {

		public FiboIterator1(long k) {
			this.k = k;
		}

		FiboIterator getNext() {
			long nextK = k + 1;
			if (nextK <= 1) {
				return new FiboIterator1(nextK);
			} else {
				return new FiboIterator2(0, 1);
			}
		}

		long getValue() {
			return k;
		}

	}

	class FiboIterator2 extends FiboIterator {

		public FiboIterator2(long fk1, long fk2) {
			this.fk1 = fk1;
			this.fk2 = fk2;
			this.fv = fk1 + fk2;
		}

		FiboIterator getNext() {
			return new FiboIterator2(fk2, fk1 + fk2);
		}

		long getValue() {
			return fv;
		}
	}

	public boolean checkIf(long requiredIlo) {
		if (requiredIlo == 0) {
			return true;
		}
		FiboIterator f1 = new FiboIterator1(1);
		FiboIterator f2 = new FiboIterator1(1);
		while (true) {
			long f1v = f1.getValue();
			long f2v = f2.getValue();
			long ilo = f1v * f2v;
			if (ilo == requiredIlo) {
				return true;
			}
			if (ilo > requiredIlo) {
				if (f1v == f2v) {
					return false;
				}
				f1 = f1.getNext();
				f2 = f1;
				if (f1.getValue() > requiredIlo) {
					return false;
				}
			} else {
				f2 = f2.getNext();
			}
		}
	}

	public static void main(String[] args) {
		BufferedReader reader = null;
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			Integer lines = Integer.valueOf(reader.readLine());
			ilo ilo = new ilo();
			for (int i = 0; i < lines; i++) {
				long toCheck = Long.valueOf(reader.readLine());
				boolean isPossible = ilo.checkIf(toCheck);
				if (isPossible) {
					System.out.println("TAK");
				} else {
					System.out.println("NIE");
				}
			}
		} catch (Throwable t) {
		} finally {
			if (reader != null) {
				try {
					reader.close();
				} catch (Throwable t) {
				}
			}
		}
	}
}