시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 44 12 2 9.524%

문제

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

이 때, nn + nm을 p로 나눈 나머지가 a가 되는 n이 존재하는지를 구하고, 존재하면 n을 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력

2
11 3 1
11 8 2

예제 출력

TAK 567
TAK 2

힌트