SNAKYNUM - 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.


Added by:Anil Kishore
Date:2011-02-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeMutants 2011 , DA-IICT, India

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.