Problem B
Barcode

To prepare for ACM-ICPC 2017 in Saigon, the host univeristy – Ho Chi Minh city University of Education (HCMUE) – decided to print barcodes on the participants’ t-shirts. The barcode requirement needs to be simple to reduce the cost but still show some scientific style. HCMUE decided that every barcode consists of red bars and blue bars satisfing at least one of the following conditions:

• The number of blue bars is equal to the number of red bars.

• There are no $2$ consecutive blue bars.

Let $K$ denote the number of different ways to create the required barcodes containing $N$ bars. Given two integers $N$ and $M$, where $M$ is a prime number, your task is to help them identify the remainder of $K$ divided by $M$.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $20$. Each dataset is described by one line containing two numbers $N$ and $M$ ($1 \leq N \leq 10^6$, $1 < M \leq 10^7$). $M$ is a prime number.

Output

For each dataset, write in one line the remainder of $K$ divided by $M$.

6
1 997
2 997
3 997
5 997
7 997
9 997

2
3
5
13
34
89