Background

This problem comes from the BZOJ April 2017 monthly contest.

Problem Description

Let $(1+\sqrt{2})^n=e(n)+\sqrt{2}f(n)$, where $e(n), f(n)$ are both integers. It is clear that $(1-\sqrt{2})^n=e(n)-\sqrt{2}f(n)$. Let $g(n)=\operatorname{lcm}(f(1),f(2),\dots,f(n))$.

Given two positive integers $n, p$, where $p$ is a prime number, and it is guaranteed that $f(1), f(2), \dots, f(n)$ are all non-zero modulo $p$, compute the value of $\sum \limits_{i=1}^n i\times g(i)$ modulo $p$.

Input Format

The first line contains a positive integer $T$, meaning there are $T$ test cases.

The following lines are the testdata. Each test case occupies one line and contains two positive integers $n$ and $p$.

Output Format

For each test case, output one line containing one non-negative integer, which is the answer for this test case.

5
1 233
2 233
3 233
4 233
5 233

1
5
35
42
121

Hint

Constraints: for $100\%$ of the testdata, $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$.

Translated by ChatGPT 5