A simple math problem

Description

As we all known，Fibonacci sequence is a sequence that fits all the requirances below：

• $f_1 = 1$

• $f_2 = 1$

• $f_n = f_{n-1} + f_{n-2}$ ($n \geq 2$ and $n \in \mathbb{N}^*$)

Please give the value of $f_n \mod p$ .

Input format

You should input $2*T + 1$ lines.

The first line is a number $T$ , which means you should solve $T$ cases .

Then , for each case :

• Line 1 : a number $n$。
• Line 2 : a number $p$。

Output format

You should output $T$ line(s).

• for each case : Output the value of $f_n \mod p$ .

Sample#1

Input Sample #1

1
5
1000000007

Output Sample #1

5

Sample #2

Input Sample #2

1
10
1000000007

Output Sample #2

55

Sample #3

Input Sample #3

10
1000000000000000000000000000000000000000000000000000000 12345
123456789098765432100 23
824935764392407465923 7843259
2934578023950234780293486780923675029378602398670293876 96753
83264589023954810 43
37294587948326591354 847356
57623487867543589 43255643354
56782222222222228364591853918549110495732510934571593720135420159509437 123456789
346567589865446786654678978654 465789
46567897654354987 3498

Output Sample #3

8940
17
4093606
60567
12
19633
22452383807
37156508
459248
959

Hint

For $30\%$ data :

• $1\le n \le 92$

For $50\%$ data :

• $1\le n < 2^{63}$
• $p = 10^9 + 7$
• $T \leq 5$

For $100\%$ data :

• $n \leq 10^{30000000}$
• $p<2^{31}$
• $T \leq 10$

Limit

• Time limit 1.00s - 3.00s
• Memory limit 128Mbit

Extra : 数据构造_小于 $10^{30000000}$ 且尽可能大的质数。