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
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	unsigned long int fibs[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 };
	const size_t fibLength = (sizeof fibs)/(sizeof fibs[0]);
	int n, t, q, i, dziel[fibLength]; bool wyn;

	cin >> t;

	for( int ti = 0; ti < t; ti++ ) {
		cin >> n;
		for( q = 0, i = fibLength-1; i>=0; i--) {
			if( n % fibs[i] == 0 ) {
				dziel[q++] = fibs[i];
			}
		}
		sort( dziel , dziel + q );
		for( i = 0, wyn = 0; i < q; i++ ) {
			if( binary_search( dziel , dziel+q , n/dziel[i] ) ) {
				cout << "TAK" << endl;
				wyn = !wyn;
				break;
			}
		}
		if( !wyn )
			cout << "NIE" << endl;
	}

	return 0;
}