Super Palindrome - 2


This problem is basically same as the previous one. You will be given two numbers, n and p. You need to output the value of (n^n)%p.

Major Constraint

Now your code should be of the form - (x)(x)(x) For example, suppose x = abc, then your code should be abcabcabc.

Update : PLEASE Check Announcements.

Input Specification

First line will contain the number of test cases, T. T test cases follow.
Each test case contains a single line containing two integers, n and p separated by space in this order.

Output Specification

For each test case output a single line containing the desired value.

Scoring Scheme

S = Length of Code.
The scoring will be relative to S.

Sample Input

3
2 3
4 5
1 5

Sample Output

1
1
1

Constraints

1 <= T <= 500
1 <= n,p <= 10^5
Time limit: 2s   Memory Limit: 32MB