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

#define  MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define  MIN(X,Y) ((X) < (Y) ? (X) : (Y))

#define MAX_INT numeric_limits<int>::max()
#define MAX_N 12
#define MAX_F 45

using namespace std;

int main()
{
  
int t;
int N[MAX_N];
int ANS[MAX_N] = {0};
int FM[MAX_F][MAX_F] = {0};
 
int maxN = 0;
  
cin >> t;
  
for(int i=0; i<t; ++i)
{
    cin >> N[i];
    maxN = MAX(maxN,N[i]);
    if(N[i]==0 || N[i]==1)
        ANS[i] = 1;
}
  
for(int i=0; i<MAX_F; ++i)
{
     FM[0][1] = FM[1][0] = 0;
}
  
FM[1][1] = 1;
for(int i=2; i<MAX_F; ++i)  
{
    FM[i][1] = FM[1][i] = FM[i-2][1] + FM[i-1][1];
     
    for(int k=0; k<t; ++k)
        if(N[k]==FM[i][1])
            ANS[k]=1;
}
  
int j;
int minS;
for(int s=2; s<=MAX_F; ++s)
{
    int min = MAX_INT;
    for(int i=2; i<=s/2; ++i)
    {
        j = s-i;
        FM[i][j] = FM[i-2][j-2] + FM[i-1][j-2] + FM[i-2][j-1] + FM[i-1][j-1];
        minS = MIN(minS, FM[i][j]);

        for(int k=0; k<t; ++k)
        if(N[k]==FM[i][j])
            ANS[k] = 1;
    }
    if(minS>maxN)
        break;
}
  
for(int i=0; i<t; ++i)
{
    if(ANS[i])
        cout << "TAK\n";
    else
        cout << "NIE\n";
}
  
return 0;
}