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
104
105
#include <cstdio>
#include <algorithm>
#include <cstring>

// POCZATEK szybkiego wczytywania

#define INPUT_BUFFER_SIZE 1000 // wejscie w tym zadaniu powinno zawierac okolo 100 znakow

inline char my_getchar()
{
	static char _input_buffer[INPUT_BUFFER_SIZE + 1];
	static int _buffer_pos = INPUT_BUFFER_SIZE;

	if (_buffer_pos == INPUT_BUFFER_SIZE) {
		int t = std::fread(_input_buffer, 1, INPUT_BUFFER_SIZE, stdin);
		_input_buffer[t] = EOF;
		_buffer_pos = 0;
	}
	return _input_buffer[_buffer_pos++];
}

inline void read_int(int &n)
{
	char c;
	bool read = false;
	n = 0;
	while (true) {
		c = my_getchar();
		if ('0' <= c && c <= '9') {
			read = true;
			n = 10 * n + c - '0';
		}
		else if (read || c == EOF) {
			break;
		}
	}
}
// KONIEC szybkiego wczytywania 

// POCZATEK szybkiego wypisywania

#define OUTPUT_BUFFER_SIZE 40 // w tym zadaniu wypiszemy maks. 4 * 10 = 40 znakow

namespace impl {
	static char _output_buffer[OUTPUT_BUFFER_SIZE];
	static int _output_buffer_pos = 0;
}

inline void my_putstring(const char s[], int len)
{
	std::memcpy(impl::_output_buffer + impl::_output_buffer_pos, s, len);

	impl::_output_buffer_pos += len;
}

void flush_buffers()
{
	fwrite(impl::_output_buffer, 1, impl::_output_buffer_pos, stdout);
}

#define PRINT_STR(str) my_putstring(str, sizeof(str) / sizeof(str[0]) - 1)

// KONIEC szybkiego wypisywania


int main()
{
	// all fibs up to 10^9 (without 0)
	const int fibs[] = { 1, 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 };
	const int fibs_len = sizeof(fibs) / sizeof(fibs[0]);

	int t;

	read_int(t);

	for (; t > 0; t--) {
		int x;
		read_int(x);

		bool res = false;

		if (x == 0)
			res = true;
		else {
			for (int i = 0; i < fibs_len; i++) {
				if (x % fibs[i] != 0)
					continue;

				const int val = x / fibs[i];

				if (std::binary_search(fibs, fibs + fibs_len, val)) {
					res = true;
					break;
				}
			}
		}

		if (res)
			PRINT_STR("TAK\n");
		else
			PRINT_STR("NIE\n");
	}

	flush_buffers();
}