A more fun version of a simpler question... :)

Each input file consists of T test cases, where each test case follows the following format:

You are given two natural numbers N and M. Write a program that outputs the remainder of the Nth Fibonacci number when divided by M.

For those who were sleeping during lesson, the Fibonacci sequence is generated as follows:

f0 = 0
f1 = 1
fi = fi-1 + fi-2 for i ≥ 2

You are supposed to output an integer fN (mod M).

Input

The first line of the input contains one integer T (1 ≤ T ≤ 100000)

The next T lines of the output contain two integers each, N and M (1 ≤ N, M ≤ 1,000,000,000).

Output

For each of the T test cases, output the integer fN (mod M).

Sample Input 1

1
3 1337

Sample Output 1

2

Sample Input 2

3
3 1337
10 1337
10 54

Sample Output 2

2
55
1

Explanation for Sample Output 1

f2 = f1 + f0 = 1 + 0 = 1
f3 = f2 + f1 = 1 + 1 = 2.