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

bool isFib(int  w)
{
       double X1 = 5 * pow(w, 2) + 4;
       double X2 = 5 * pow(w, 2) - 4;

       long X1_sqrt = (long)sqrt(X1);
       long X2_sqrt = (long)sqrt(X2);

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

int main()
{

    int t;
    div_t divresult;


    scanf("%d", &t);



    for(int i=0; i<t; i++)
    {
        bool found = false;
        int n;

        scanf("%d", &n);

        if(isFib(n) || n==0)
        {
            printf("TAK\n");
            continue;
        }

        int d=n;
        int f1=1;
        int f2=1;

        for(int tmp=0; tmp<n && tmp<d; )
        {
            tmp = f1+f2;

            divresult = div (n,tmp);
            d = divresult.quot;

            if(divresult.rem == 0 && isFib(d))
            {
                printf("TAK\n");
                found = true;
                break;
            }

            f1 = f2;
            f2 = tmp;
        }

        if(found == false)
        {
            printf("NIE\n");
        }
    }

    return 0;
}