At midnight, I dare not look back when crossing the overpass, where it used to be bustling with traffic, now lies the River of Forgetfulness under my feet.
--- Out of the Mountains

Problem Description

Given two positive integers $n$ and $p$, where $p$ is a prime number, it is guaranteed that for all positive integers $n$, $(1+\sqrt{2})^n$ can be expressed as $e(n) + \sqrt{2} f(n)$, where $e(n)$ and $f(n)$ are integers, and $f(n)$ is not zero modulo $p$. Obviously, $(1-\sqrt{2})^n = e(n) - \sqrt{2} f(n)$. Let $g(n) = \operatorname{lcm}(f(1), f(2), \dots, f(n))$.

Given $n$ and $p$, calculate the value of $\sum \limits_{i=1}^n i \times g(i)$ modulo $p$.

Input Format

• The first line contains a positive integer $T$, representing the number of test cases.
• The next $T$ lines each contain two positive integers $n$ and $p$.

Output Format

For each test case, output a single non-negative integer representing the answer for that test case.

Sample Input

5
1 233
2 233
3 233
4 233
5 233

Sample Output

1
5
35
42
121

Hints

Data Size and Constraints

For 100% of the data, $1 \leq T \leq 210$, $1 \leq n \leq 10^6$, $2 \leq p \leq 10^9+7$, $\sum n \leq 3 \times 10^6$.