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
#include <cstdio>
#define uint unsigned int

#define MAX 1000000000

uint F[100];
int sizeF;
void genF()
{
    F[0]=0;
    F[1]=1;
    for(sizeF=2;F[sizeF-1]<=MAX;sizeF++)
    {
        F[sizeF]=F[sizeF-1]+F[sizeF-2];
    }
}

bool findF(int v)
{
    int l=0,r=sizeF-1;
    while(l!=r)
    {
        int p=(l+r)/2;
        if(v<=F[p])
        {
            r=p;
        }else
        {
            l=p+1;
        }
    }
    return F[l]==v;
}

int main()
{
    genF();
    int t;
    scanf("%d",&t);
    LABEL:
    while(t--)
    {
        int n;
        scanf("%d",&n);
        if(n==0)
        {
            printf("TAK\n");
            continue;
        }
        for(int a=1;F[a]<=n;++a)
        {
            if(n%F[a]==0)
            {
                if(findF(n/F[a]))
                {
                    printf("TAK\n");
                    goto LABEL;
                }
            }
        }
        printf("NIE\n");
    }
    return 0;
}