Fibonacci numbers are given by 

• f(n) = f(n-1) + f(n-2)

with f(0) = 0 and f(1) = 1.

first number of series ------ 0  1  1  2  3  5  8  13 

Now let's have a new series called "Fibonacci Twist" which is given by 

• ft(n) = ft(n-1) + ft(n-2) + (n-1)

with ft(0) = 0 and ft(1) = 1.

with first few number in the series ----- 0  1  2  5  10  19  34  59 

Now your task is to find ft(n).

Since the number can be big you have to find the result mod M.

Input

first line having single number 't' -- number of test cases.

Next t lines have 2 number each 'n' and 'M'

Output

Single number given the n-th term mod M

Example

Input:
3
5 20
10 77
15 111

Output:
19
45
69

Constraints

• 10 <= t <= 100
• 0 <= n <= 10^9
• 100 <= M <= 10^9

Explanation

1. ft(5) is 19. 19 % 20 = 19
2. ft(10) is 276. 276 % 77 = 45
3. ft(15) is 3177. 3177 % 111 = 69