题目描述

令 $(1+\sqrt 2)^n=e(n)+\sqrt 2f(n)$，其中 $e(n),f(n)$ 都是整数，显然有 $(1-\sqrt 2)^n=e(n)-\sqrt 2f(n)$。令 $g(n)$ 表示 $f(1),f(2),\cdots f(n)$ 的最小公倍数，给定两个正整数 $n$ 和 $p$,其中 $p$ 是质数，并且保证 $f(1),f(2),\cdots f(n)$ 在模 $p$ 意义下均不为 $0$,请计算 $\sum\limits_{i=1}^ni\times g(i)$ 其在模 $p$ 的值。

输入格式

第一行包含一个正整数 $T$ ，表示有 $T$ 组数据。

接下来是测试数据。每组测试数据只占一行，包含两个正整数 $n$ 和 $p$ 。

输出格式

对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。

样例输入

5
1 233
2 233
3 233
4 233
5 233

样例输出

1
5
35
42
121

数据范围与约定

对于 $100\%$ 的数据，$1\le T\le 210$，$1\le n\le 10^6$，$2\le p\le 10^9+7$，$\sum n\le 3\times 10^6$。

题目来源

鸣谢 Tangjz 提供试题