Govind is very fond of playing with binary sequences. One day his brother Mukund challenged him to solve a problem on binary sequences. Since Govind do not have time to solve the problem, he needs your assistance. Help him find the answer to the problem.

The problem is as follows:

A function f(x) is defined such it is equal to the number of binary sequences of length x that do not contain pattern 11.

For example:

• f(1) = 2 (the only sequences possible are 0, 1)
• f(3) = 5 (the sequences are 000, 001, 010, 100, 101)

Another function S(n) is defined such that

S(n) = f(1) + f(2) + f(3) + ... + f(n-1) + f(n)

Your task is to find the value of S for the given values of n.

As the S(n) can get too large, you have to print the result mod M

Input

First line of input contains an intger t (number of test cases.)

Then follows t lines each containing 2 space separated numbers n and M.

Output

For each test case output a single integer S(n) mod M.

Constraints

t <= 100

1 <= n, M <= 10^8

Example

Input:
2
1 107
3 2

Output:
2
0