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
#include<cstdio>

using namespace std;

const int ZAKR=1000*1000*1007;

int FIB[57];

void genfib(int zakr)
{
    FIB[0]=FIB[1]=1;
    int i=1;
    while(FIB[i]<zakr)
    {
        FIB[i+1]=FIB[i]+FIB[i-1];
        i++;
    }
}

bool spr(int a)
{
    int j=44;
    for(int i=1;i<=j;i++)
    {
        if(a%FIB[i]==0)
            {
                int pom=a/FIB[i];
                for(;pom<FIB[j];j--)
                {
                }
                if(FIB[j]==pom)
                    return true;

            }

    }
    return false;
}

int main()
{
    int t,a;
    genfib(ZAKR);
    scanf("%d",&t);
    for(int i=0;i<t;i++)
    {
        scanf("%d",&a);
        if(spr(a))
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}