bzoj#P4833. [Lydsy2017年4月月赛]最小公倍佩尔数

[Lydsy2017年4月月赛]最小公倍佩尔数

题目描述

(1+2)n=e(n)+2f(n)(1+\sqrt 2)^n=e(n)+\sqrt 2f(n),其中 e(n),f(n)e(n),f(n) 都是整数,显然有 (12)n=e(n)2f(n)(1-\sqrt 2)^n=e(n)-\sqrt 2f(n)。令 g(n)g(n) 表示 f(1),f(2),f(n)f(1),f(2),\cdots f(n) 的最小公倍数,给定两个正整数 nnpp,其中 pp 是质数,并且保证 f(1),f(2),f(n)f(1),f(2),\cdots f(n) 在模 pp 意义下均不为 00,请计算 i=1ni×g(i)\sum\limits_{i=1}^ni\times g(i) 其在模 pp 的值。

输入格式

第一行包含一个正整数 TT ,表示有 TT 组数据。

接下来是测试数据。每组测试数据只占一行,包含两个正整数 nnpp

输出格式

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

样例输入

5
1 233
2 233
3 233
4 233
5 233

样例输出

1
5
35
42
121

数据范围与约定

对于 100%100\% 的数据,1T2101\le T\le 2101n1061\le n\le 10^62p109+72\le p\le 10^9+7n3×106\sum n\le 3\times 10^6

题目来源

鸣谢 Tangjz 提供试题