N과 M
시간 제한1초메모리 제한1024 MB
N, N^N, N^{N^N}, ... 거듭제곱 탑을 M으로 나눈 나머지가 나중에 고정된 값을 구합니다. N과 M은 10^9 이하입니다.
문제
임의의 자연수 N과 M이 주어져 있다. 를 A의 B승이라고 할 때, 수열 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있을 때, 이 일정한 나머지 값을 계산하라.
입력
첫 번째 줄에는 질의의 개수 T가 주어진다. 질의는 1개 이상 1000개 이하이다.
두 번째 줄부터 T+1번째 줄까지는 각 질의에 해당하는 자연수 N과 M이 주어진다. N과 M은 둘 다 이하이다.
출력
각 질의의 N과 M에 대해, 의 값을 M으로 나눈 나머지를 구하여라. 나머지의 값은 0 이상 M 미만이어야 한다.