[Lydsy2017年4月月赛]最小公倍佩尔数
时间限制：8s 空间限制：128MB
题目描述
令(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
提示
没有写明提示
题目来源
鸣谢Tangjz提供试题