양의 정수 m과 소수 p, 그리고 p로 나누었을 때의 나머지 a가 주어진다.

이때, nⁿ + n^m을 p로 나눈 나머지가 a가 되는 양의 정수 n이 존재하는지를 구하고, 존재하면 n을 구하는 프로그램을 작성하시오.

입력 형식

입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫째 줄에는 테스트 케이스의 개수 d (1 ≤ d ≤ 300)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 세 정수 p, a, m이 주어진다. (2 ≤ p ≤ 10⁹, 0 ≤ a < p, 1 ≤ m ≤ 20, m < p) p는 항상 소수이다. 

출력 형식

문제의 조건에 해당하는 n < 10¹⁰⁰⁰이 존재하면, "TAK n"을 출력하고, 존재하지 않는 경우에는 "NIE"를 출력한다.

예제 입력

2
11 3 1
11 8 2

예제 출력

TAK 567
TAK 2