The Fibonacci numbers are a well-known sequence of integers defined recursively:

$$F_k = \begin{cases} k & \text{for } k \in \{0, 1\} \\ F_{k-1} + F_{k-2} & \text{for } k > 1 \end{cases}$$

Here are the first few terms of this sequence:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$

In this task, we want to check whether a given integer can be written as the product of two Fibonacci numbers.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10$), representing the number of test cases to consider. This is followed by $t$ lines; the $i$-th of these contains a single integer $n_i$ ($0 \le n_i \le 10^9$).

Output

Your program should output exactly $t$ lines. The $i$-th line should contain the word TAK or NIE, depending on whether the number $n_i$ can be represented as the product of two Fibonacci numbers.

Examples

Input 1

5
5
4
12
11
10

Output 1

TAK
TAK
NIE
NIE
TAK