题目背景

题目来自 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$。

输出格式

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

5
1 233
2 233
3 233
4 233
5 233

1
5
35
42
121

提示

对于 $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$。