N의 존재

소수 $p$, 양의 정수 $m$, 그리고 $0 \le a < p$인 정수 $a$가 주어진다.

$n^n + n^m \equiv a \pmod{p}$를 만족하는 양의 정수 $n$이 존재하는지 판별하여라.

첫째 줄에 테스트 케이스의 개수 $d$ ($1 \le d \le 300$)가 주어진다.

이어지는 $d$개의 줄에는 각각 세 정수 $p$, $a$, $m$이 공백으로 구분되어 주어진다. ($2 \le p \le 10^9$, $0 \le a < p$, $1 \le m \le 20$, $m < p$) $p$는 항상 소수이다.

각 테스트 케이스마다 한 줄씩 출력한다. $n < 10^{1000}$ 범위에서 $n^n + n^m \equiv a \pmod{p}$를 만족하는 양의 정수 $n$이 존재하면 TAK을, 존재하지 않으면 NIE를 출력한다.