To prepare for ACMICPC 2017 in Saigon, the host univeristy
â€“ Ho Chi Minh city University of Education (HCMUE) decided to
print barcodes in the participantsâ€™ tshirts. 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:
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$.
Sample Input 1 
Sample Output 1 
6
1 997
2 997
3 997
5 997
7 997
9 997

2
3
5
13
34
89
