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 #include #include #include #include #include using namespace std; typedef vector VI; typedef long long LL; typedef pair PII; #define FOR(x, b, e) for (int x = b; x <= (e); ++x) #define FORD(x, b, e) for (int x = b; x >= (e); --x) #define REP(x, n) for (int x = 0; x < (n); ++x) #define VAR(v, n) __typeof(n) v = (n) #define ALL(c) (c).begin(), (c).end() #define SIZE(x) ((int) (x).size()) #define FOREACH(i, c) for (VAR(i, (c).begin()); i != (c).end(); ++i) #define PB push_back #define ST first #define ND second #define MP make_pair #define INF 1000000001 const int MAX = 1000000000; int main() { VI fib; fib.PB(1); fib.PB(1); while (fib.back() < MAX) fib.PB(fib[SIZE(fib) - 2] + fib[SIZE(fib) - 1]); //REP(i, SIZE(fib)) printf("fib[%d] = %lu\n", i, fib[i]); int t, n, n2; for (scanf("%d\n", &t); t > 0; --t) { scanf("%d\n", &n); bool res = (n == 0); for (int i = 0; fib[i] <= n && !res; ++i) if (n % fib[i] == 0) { n2 = n / fib[i]; for (int j = 0; fib[j] <= n2 && !res; ++j) { res = (n2 == fib[j]); } } printf(res ? "TAK\n" : "NIE\n"); } return 0; }