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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <stdio.h>

int d[] = {
            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
};

int find(int d[], int size, int v)
{
    int l = 0;
    int r = size - 1;
    int m;

    while (l <= r)
    {
        m = (l + r) >> 1;
        if (d[m] < v)
        {
            l = m + 1;
        }
        else if (d[m] > v)
        {
            r = m - 1;
        }
        else
        {
            return m;
        }
    }
    return -1;
}

int main(void)
{
    int t, n, l, i, r;

    l = sizeof(d)/sizeof(d[0]);

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        r = -1;
        for (i = 0; (i < l) && (r == -1) && (d[i] <= n); ++i)
        {
            if ((n % d[i]) == 0)
            {
                r = find(d, l, n/d[i]);
            }
        }
        if (r != -1)
        {
            printf("TAK\n");
        }
        else
        {
            printf("NIE\n");
        }
    }

    return 0;
}