P10663 BZOJ4833 最小公倍佩尔数

题目来自 BZOJ 2017 年 4 月月赛。

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

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

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

对于 $100\%$ 的数据，$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$。