第一行包含一个正整数 T ，表示有 T 组数据，满足 T≤210 。接下来是测试数据。每组测试数据只占一行，包含
两个正整数 n 和 p ，满足 1≤n≤10^6,2≤p≤10^9+7 。保证所有测试数据的 n 之和不超过 3×10^6 。
BZPRO令(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(
对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。
5
1 233
2 233
3 233
4 233
5 233
1
5
35
42
121