Problem Description

The Fibonacci sequence is defined as follows:

$$\operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases}$$

Now we define a function (note that when $n<1$, the value of this function is $0$):

$$f(n)=\sum_{i=1}^n\operatorname{fib}^2(i)$$

Since computing the prefix sum of the Fibonacci sequence is too easy, you need to compute:

$$\sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))$$

The answer should be taken modulo the given $p$.

Note: $\operatorname{fib}^2(x)$ means the square of $\operatorname{fib}(x)$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case, a line contains two integers $n,p$.

Output Format

For each test case, output one integer per line, the result modulo $p$.

3
2 100
3 100
4 100

4
18
60

Hint

Sample explanation:

For the first test case, $1\times(0+1^2+1)+1\times(0+1^2+1)=4$.

For the second test case, $1\times(0+1^2+1)+1\times(0+1^2+1)+2\times(1+2^2+2)=18$.

Constraints

This problem uses bundled tests.

• Subtask 1 (5 points): $n \le 10^7$, $p=10^9+7$.
• Subtask 2 (20 points): $T\le 10^4$, $n \le 10^8$, $p=10^9+7$.
• Subtask 3 (5 points): $p=2$.
• Subtask 4 (15 points): $p\le 5$.
• Subtask 5 (30 points): $T\le 10^4$, $n \le 10^8$.
• Subtask 6 (25 points): no special constraints.

For all testdata, $1\le T\le 2\times 10^5$, $1\le n\le 10^{18}$, $2\le p\le 10^9+7$。

Translated by ChatGPT 5