Super Palindrome - 1

The problem is quite simple. You will be given two numbers, n and p. You need to output the value of (n^n)%p.

Major Constaints

Your code should be of the form - (x[1 : (length(x)-1)])(x)(Reverse(x)).
x[1:length(x)-1] = Skip First and last character of string x.
For example, suppose x = abc, then your code should be babccba. The length of x should always be greater than 2.

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 <= 50
1 <= n,p <= 10^18
Time limit: 2s   Memory Limit: 32MB