夜半三更过天桥从来不敢回头看,白日里是车水马龙此时脚下是忘川.
---出山

题目描述

给定两个正整数 $n$ 和 $p$，其中 $p$ 是质数，并且保证对于所有的正整数 $n$，$(1+\sqrt{2})^n$ 都可以表示为 $e(n) + \sqrt{2} f(n)$，其中 $e(n)$ 和 $f(n)$ 都是整数，且 $f(n)$ 在模 $p$ 意义下不为 $0$。显然有 $(1-\sqrt{2})^n = e(n) - \sqrt{2} f(n)$。令 $g(n) = \operatorname{lcm}(f(1), f(2), \dots, f(n))$。

给定 $n$ 和 $p$，请计算 $\sum \limits_{i=1}^n i \times g(i)$ 模 $p$ 的值。

输入格式

第一行包含一个正整数 $T$，表示有 $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$。