8649번 - Iloczyn 다국어

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.