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

#define FIBO 42
#define F(x) fibo[x]

#define YES printf("TAK\n")
#define NO printf("NIE\n")

inline int pos(const long * fibo, const long &x) {
	for(int i = 1; i < FIBO; ++i)
		if(F(i) > x)
			return --i;
}

int main() {

	long x, fibo[] = {
		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 i, n, p, divs;
	scanf("%d", &n);

	while(n--) {
		scanf("%ld", &x);

		// Szukam pozycję liczby fibo mniejszej bądź równej x.
		p = pos(fibo, x);
		
		// Jeśli x jest liczbą fibonacciego to spełnia warunek dla iloczynu 1 * x.
		if(fibo[p] == x) {
			YES;
			continue;
		}

		// Szukam dwóch dzielników
		divs = 0;
		while( x > 1 ) {
			for(i = p; i >= 0; --i) {
				if(x % F(i) == 0) {
					if(++divs > 2) 
						goto end;
					x /= F(i);
					p = pos(fibo, x);
					break;
				} else if(i == 0) goto end;
			}
		}
		YES;
		continue;
end:
		NO;
	}

	return (0);
}