Sanky is a school kid and is very fond of numbers. His teacher gave his class a home work, asking each of them to invent a new series of numbers, with a large collection of numbers in them. His friend Evan has already invented one, which starts from 0 and picks every alternate number : {0, 2, 4 ,...} and he named them 'Evan' numbers :). Sanky is not happy because he couldn't invent that first and thinks picking every alternate number starting from 1 : {1, 3, 5, ... } would not be very odd ;).

The answer may get very big and not fit in Sanky's book, so please just tell him the ( answer modulo M )

Input

First line contains T [ number of test cases, around 50 ]. Each of the next T lines contains two integers N M.

1 <= N <= 1,000,000,000

2 <= M <= 1,000,000,007

Output

For each test case, output ( Number of Snaky numbers of length at most N ) % M, in a separate line

Example

Input:
3
1 101
2 107
3 1001

Output:
10
91
616

Hint: You may have to use the mod operator wisely !

* There are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted.