서로 다른 정수의 곱

양의 정수 $n$이 주어질 때, 이 수를 서로 다른 $k$개의 양의 정수의 곱으로 나타낼 수 있는지 판별하세요.

즉, 모두 서로 다른 양의 정수 $a_1, a_2, \ldots, a_k$를 사용하여 $n = a_1 \times a_2 \times \cdots \times a_k$가 성립하는 표현이 존재하는지 확인합니다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 4000$)가 주어집니다.

다음 $t$개의 줄에는 각각 두 정수 $n$과 $k$ ($1 \le n \le 10^9$, $1 \le k \le 20$)가 공백으로 구분되어 주어집니다.

정확히 $t$개의 줄을 출력합니다. $i$번째 줄에는 $i$번째 $n$을 서로 다른 $k$개의 양의 정수의 곱으로 나타낼 수 있으면 TAK을, 그렇지 않으면 NIE를 출력합니다.