记录编号	282380	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	5.246 s
提交时间	2016-07-13 15:27:53	内存使用	0.31 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#define ull long long

namespace sasa{
	ull read(){
		ull x=0, f=1; char ch;
		while(ch<'0'||ch>'9'){
			if(ch=='-')f=-1;
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
			x =x*10+ch-'0', ch=getchar();
		return x*f;
	}
	ull N, mod;

	struct Matrix{
		ull n, m, a[3][3];
		void clear(){n=m=0; memset(a, 0, sizeof(a));}
		inline Matrix operator * (const Matrix& x) {
			if(m != x.n) printf("* error\n"), abort();
			Matrix tmp; tmp.clear();
			tmp.n = n; tmp.m = x.m;
			for(int i=0; i<tmp.n; ++i)
				for(int j=0; j<tmp.m; ++j)
					for(int k=0; k<m; ++k)
						tmp.a[i][j] += (a[i][k]*x.a[k][j])%mod, tmp.a[i][j] %= mod;
			
			return tmp;
		}
	};
}
using namespace sasa;
int main()
{
	freopen("eins.in","r",stdin); freopen("eins.out","w",stdout);
	ull sets = read();
	Matrix I;
	I.n = I.m = 2; I.a[0][0] = I.a[1][1] = 1;
				   I.a[1][0] = I.a[0][1] = 0;
	Matrix first;
	first.n = 1, first.m = 2; first.a[0][0] = first.a[0][1] = 1;
	Matrix x;
	x.n = x.m = 2; x.a[0][0] = x.a[1][0] = x.a[0][1] = 1; x.a[1][1] = 0;
	Matrix ff, xx, y;
	while(sets--){
		N = read(), mod = read();
		if(N==0 || mod==1){puts("0"); continue;}
		if(N==1){puts("1"); continue;}
		xx = x;
		y = I;
		for(N-=2; N; N>>=1, xx=xx*xx) 
			if(N&1) y = y*xx;
		printf("%lld\n", (first*y).a[0][0]%mod);
	}
	
//	while(1);
	return 0;
}