Pretty Cake

Time limit1sMemory limit1024 MB

Summary

For each N, decide whether the base can be an a by b rectangle with a times b equal to N and a plus b divisible by 3.

Level: Medium4 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

Today, December 31, is Jongseo's birthday, and Good Bye 2021! opens today. $N$ friends want to make a pretty cake as a birthday present for Jongseo.

Here, a pretty cake is a cake that satisfies the following conditions.

The cake is a rectangular box with height $1$ and volume $N$ .
You must be able to cut the cake into $N$ cube-shaped pieces, each with side length $1$ .
You must be able to wrap a band, made by joining rectangles of width $1$ side by side, around the side of the cake with no gaps.
The decorative band must show red, green, and white rectangles of width $1$ , in that order and repeating, with the same number of each color.

For example, the figure below shows one pretty cake for $N = 8$ and the band used with it.

Pretty cake figure

Cake band example

Depending on the value of $N$ , a pretty cake may not be possible. Determine whether a pretty cake with volume $N$ can be made for each of Jongseo's friends.

Input

The first line contains an integer $T$ , the number of test cases.

Each of the next $T$ lines contains one integer $N$ , as defined in the problem.

Output

Print $T$ lines, one answer per line.

Print TAK if a pretty cake with volume $N$ can be made, and NIE otherwise.

Constraints

$1 \le T \le 1\,000$
$1 \le N \le 10^{18}$
All numbers in the input are integers.

Examples1

Example 1
Input
```
3
2
9
10
```
Expected output
```
TAK
TAK
NIE
```