The problem is simple. Find (a^b) % MOD.

where, a = Nth non-Fibonacci number, b = Nth Fibonacci number.

Consider Fibonacci series as 1, 1, 2, 3 ...

Input

First line contains T, the number of test cases. Each of the next T lines contains two numbers N and M where M is a prime number.

Output

Print T lines of output where each line corresponds to the required answer.

Example

Input:
3
3 1000000007
2 13
1 13

Output:
49
6
4

Explanation

For N = 3: 3rd non Fibonacci number = 7, 3rd Fibonacci number = 2. Answer = (7^2) % 1000000007 = 49

For N = 2: 2nd non Fibonacci number = 6, 2nd Fibonacci number = 1. Answer = (6^1) % 13 = 6

For N = 1: 1st non Fibonacci number = 4, 1st Fibonacci number = 1. Answer = (4^1) % 13 = 4

If you are getting TLE here you may try easy version of this POWFIB.

Constraints

1 <= T <= 50000

1 <= N <= 1e16

2 <= M <= 1e18, and M is a prime number.

Note:: My best time with C++ with fully optimized code is 1.18s.

Have fun :)