Problem Description

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

Input Format

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain two integers $n, k$.

Output Format

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

3
15 2
24 4
24 5

TAK
TAK
NIE

Hint

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