Product of Distinct Integers

Given a positive integer $n$, determine whether it can be written as a product of $k$ distinct positive integers.

In other words, decide whether there exist positive integers $a_1, a_2, \ldots, a_k$, all different from one another, such that $n = a_1 \times a_2 \times \cdots \times a_k$.

The first line contains a single integer $t$ ($1 \le t \le 4000$), the number of test cases.

Each of the next $t$ lines contains two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 20$), separated by a space.

Print exactly $t$ lines. On the $i$-th line print TAK if the $i$-th value $n$ can be represented as a product of $k$ distinct positive integers, or NIE otherwise.