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
#include <iostream>
#include <math.h>

static int Fibo[44] = {0, 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 };
class ilo
{
public:

	void IloFibo(int wartosci[])
	{
		for (int i = 0; i < wartosci[0]; i++)
		{
			if (IsFiboIloczyn(wartosci[i + 1])) std::cout << "TAK" << std::endl;
			else std::cout << "NIE" << std::endl;
		}
	}

	bool IsFiboIloczyn(int wartosc)
	{
		int i = 2;
		int newValue = wartosc;
		if (IsFibo(newValue)) return true;
		while (i < 44)
		{
			newValue = wartosc / Fibo[i];
			if (newValue*Fibo[i] == wartosc && IsFibo(newValue))
			{
				return true;
			}
			if (newValue < Fibo[i])
			{
				return false;
			}
			i++;
		}
		return false;

	}
	bool IsFibo(int Value)
	{
		for (int i = 0; i < 44; i++)
		{
			if (Value == Fibo[i]) return true;
		}
		return false;
	}


};

int main(int argc, char *argv[])
{
	int first;
	ilo zadanie;
	std::cin >> first;
	int* wartosciZadanie = new int[first+1];
	wartosciZadanie[0] = first;
	for (int i = 1; i <= first; i++)
	{
		int tmp;
		std::cin >> tmp;
		wartosciZadanie[i] = tmp;
	}
	zadanie.IloFibo(wartosciZadanie);
	return 0;
}