P5973 [PA 2013] Iloczyn

Given positive integers $n$ and $k$, determine whether $n$ can be factored into a product of $k$ distinct positive integers.

The first line contains an integer $T$, the number of test cases. The next $T$ lines each contain two integers $n, k$.

Output $T$ lines. If $n$ can be factored as required, output `TAK`; otherwise output `NIE`.

Constraints: for $100\%$ of the testdata, $1 \le T \le 4 \times 10^3$, $1 \le n \le 10^9$, $1 \le k \le 20$. Translated by ChatGPT 5