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⁹
• 100 ≤ M ≤ 10⁹

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