Dla danej liczby całkowitej dodatniej $n$, zastanawiamy się, czy możemy ją przedstawić jako iloczyn $k$ różnych liczb całkowitych dodatnich.

Input Format

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 4\,000$), oznaczającą liczbę przypadków testowych do rozważenia. Każdy z kolejnych $t$ wierszy zawiera dwie liczby całkowite $n_{i}$ oraz $k_{i}$ ($1 \le n_{i} \le 10^{9}$, $1 \le k_{i} \le 20$).

Output Format

Twój program powinien wypisać na wyjście dokładnie $t$ wierszy. W $i$-tym z tych wierszy powinno znaleźć się jedno słowo TAK lub NIE, w zależności od tego, czy liczbę $n_{i}$ można przedstawić jako iloczyn $k_{i}$ różnych czynników.

Examples

Input

3
15 2
24 4
24 5

Output

TAK
TAK
NIE