Snaky Numbers
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 ;).
|
After refreshing at home, he comes up with a new series of numbers in which the digits alternate between increasing and decreasing when compared with the digit before it, in a zig-zag fashion. To make it clear, if the number is abcde, either a < b > c < d > e or a > b < c > d < e. He cleverly named them 'Snaky Numbers' :). Eg: 8, 90, 243516 and 31524 are Snaky while 44, 123 and 4235 are not. He is now wondering if his Snaky series is large enough. Particularly, he wants to know how many 'Snaky Numbers' are there of length at most N. Count only non-negative integers, without leading zeros. |
|
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.