#4833. [Lydsy1704月赛]最小公倍佩尔数

内存限制:128 MiB 时间限制:8 Sec

题目描述

 令(1+sqrt(2))^n=e(n)+f(n)*sqrt(2),其中e(n),f(n)都是整数,显然有(1-sqrt(2))^n=e(n)-f(n)*sqrt(2)。令g(

n)表示f(1),f(2)…f(n)的最小公倍数,给定两个正整数n和p,其中p是质数,并且保证f(1),f(2)…f(n)在模p意义
下均不为0,请计算sigma(i*g(i)),1<=i<=n.其在模p的值。

输入格式

第一行包含一个正整数 T ,表示有 T 组数据,满足 T≤210 。接下来是测试数据。每组测试数据只占一行,包含
两个正整数 n 和 p ,满足 1≤n≤10^6,2≤p≤10^9+7 。保证所有测试数据的 n 之和不超过 3×10^6  。

输出格式

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

样例

样例输入


			
5
1 233
2 233
3 233
4 233
5 233

样例输出


			
1
5
35
42
121

数据范围与提示