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
// Krzysztof Baranski
////////////////////////////////////////////////////////////////////
//                                                                //
//                           HEADERS                              //
//                                                                //
//////////////////////////////////////////////////////////////////// 
// includes
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <complex>
#include <iterator>
#include <set>
#include <bitset>
#include <map>
#include <stack>
#include <list>
#include <queue>
#include <deque>
#include <cstdlib>
using namespace std;
// defines
#define FOR(x,b,e) for(int x=b; x<=(e); ++x)
#define FORD(x,b,e) for(int x=(b); x>=(e); --x)
#define FORK(x,b,e,k) for(int x=b; x<=(e); x+=k)
#define REP(x,n) for(int x=0; x<(n); ++x)
#define VAR(v,n) decltype(n) v=(n)
#define ALL(c) c.begin(),c.end()
#define SIZE(x) (int)x.size()
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define CLEAR(x) while(!(x).empty())(x).pop()
#define PB push_back
#define MP make_pair
#define ND second
#define ST first
#define POP(q) q.top(); q.pop()

#define __START__ int __z_;scanf("%d\n",&__z_);while(__z_--){
#define __STOP__ }return 0;
#define _INT(x) int x; scanf("%d",&x) 
// typedef
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VLL;
typedef vector<bool> VB;
typedef stack<int> SI;
typedef pair<int,int> PII;
typedef stack<PII> SPII;
typedef vector<char> VC;
typedef vector<VC> VVC;
// consts
const int INF = 1000000001;
const long long LINF = 1000000000000000001;
const double EPS = 10e-9;
////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------//
////////////////////////////////////////////////////////////////////

const VLL fibbs = {0,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};

//==================================================================| MAIN
int main() {
	__START__
	
	LL n;
	scanf("%lld",&n);
	
	bool ok=false;
	for(int i=0; fibbs[i]<=n;++i) {
		int begin=0,end=SIZE(fibbs);
		while(begin<end) {
			int m=(begin+end)/2;
			if(fibbs[i]*fibbs[m]<n)
				begin=m+1;
			else
				end=m;
		}
		if(fibbs[i]*fibbs[begin]==n) {
			printf("TAK\n");
			ok=true;
			break;
		}
	}
	
	if(!ok) printf("NIE\n");
	
	__STOP__
}