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
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;


public class ilo {

	public static void main(String[] args) throws IOException {
		
		ilo solver = new ilo();
		solver.init();
		solver.solve();
	}
	
	final static int SIZE = 45;
	
	int[] f = new int[SIZE];
	Set<Integer> fSet = new HashSet<Integer>();
	
	void init() {
		f[1] = 1;
		for (int k = 2; k < SIZE; k++) f[k] = f[k-1] + f[k-2];
		for (int k : f) fSet.add(k);
		//printF();
	}
	
	private void printF() {
		for (int k : f) System.out.println(k + "\t");
		System.out.println();
	}

	void solve() throws IOException { 
		Reader in = new Reader(System.in);
		PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
		for (int T = in.nextInt(); T > 0; T--) {
			int n = in.nextInt();
			if (isOk(n)) {
				out.println("TAK");
			} else {
				out.println("NIE");
			}
		}
		
		out.flush();
		out.close();
	}
	
	private boolean isOk(int n) {
		if (n <= 3) return true;
		
		for (int i = 1; i < SIZE; i++) {
			int d = n/f[i];
			if (d * f[i] == n && fSet.contains(d)) {
				return true;
			}
		}
		return false;
	}

	private static class Reader {
	    BufferedReader reader;
	    StringTokenizer tokenizer;

	    /** call this method to initialize reader for InputStream */
	    Reader(InputStream input) {
	        reader = new BufferedReader(
	                     new InputStreamReader(input) );
	        tokenizer = new StringTokenizer("");
	    }

	    public void skipLine() throws IOException {
			reader.readLine();
		}

		/** get next word */
	    public String next() throws IOException {
	        while ( ! tokenizer.hasMoreTokens() ) {
	            //TODO add check for eof if necessary
	            tokenizer = new StringTokenizer(
	                   reader.readLine() );
	        }
	        return tokenizer.nextToken();
	    }

	    public int nextInt() throws IOException {
	        return Integer.parseInt( next() );
	    }
	    
	    public double nextDouble() throws IOException {
	        return Double.parseDouble( next() );
	    }
	    
	    public long nextLong() throws IOException {
	    	return Long.parseLong(next());
	    }
	}
}