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

입력 형식

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

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

출력 형식

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

예제 입력

4
1 1
3 4
28 43
370 205

예제 출력

0
3
36
165