8 人解决，34 人已尝试。
11 份提交通过，共有 139 份提交。
8.3 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
f(0)=0;
f(1)=1;
f(n)=f(n-1)+f(n-2);
对于这个数列有很多神奇的性质，比如
f(n) 与 f(n-1) 是互质的，因为 gcd(f(n),f(n-1))=gcd(f(n-1),f(n-2))…=gcd(f(2),f(1))=1;
比如当 n 接近无穷大的时候，f(n)/f(n-1)-> 黄金比例 .
有一天实验室的 Castor 突发奇想，给出 f(k*n)=0 (mod f(n)^2) 中 n 的大小，能否知道最小的 k, 可以满足这个式子呢？Castor 冥思苦想，还是不得其解，由于 ECNU 的孩子都喜欢探索，于是他来请教你，但是他不想直接得到答案，而是希望你给他 1+2+…k 的和提示他一下。由于这个和可能很大，所以只要给出模 m 的余数即可。
第一行为一个整数 T, 表示测数数据的组数 .
接下来 T 行，每行给出 2 个整数 n(0<n<=1000,000,000), m(0<m<=1000000)
输出一个和 (1+2+..k)(取余后的数).
每个输出占一行。
2 1 100 100 2009
1 1476
8 人解决，34 人已尝试。
11 份提交通过，共有 139 份提交。
8.3 EMB 奖励。