시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 65 9 9 40.909%

문제

임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있을 때, 이 일정한 나머지 값을 계산하라.

입력

첫 번째 줄에는 질의의 개수 T가 주어진다. 질의는 1개 이상 1000개 이하이다.

두 번째 줄부터 T+1번째 줄까지는 각 질의에 해당하는 자연수 N과 M이 주어진다. N과 M은 둘 다 10^9 이하이다.

출력

각 질의의 N과 M에 대해, N^(N^(N^(N^...))의 값을 M으로 나눈 나머지를 구하여라. 나머지의 값은 0 이상 M 미만이어야 한다.

예제 입력 1

4
1 1
3 4
28 43
370 205

예제 출력 1

0
3
36
165