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

입력 형식

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą t (1 ≤ t ≤ 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 ≤ n_i ≤ 10⁹, 1 ≤ k_i ≤ 20).

출력 형식

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.

예제 입력

3
15 2
24 4
24 5

예제 출력

TAK
TAK
NIE