记录编号	292538	评测结果	AAAAAAAAAA
题目名称	eins	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	2.683 s
提交时间	2016-08-08 23:09:46	内存使用	0.29 MiB

/*
| A B | *| 1 1 |=| A+B A|
| 1 1 |  | 1 0 | | 1  1 |
*/
#include<cstdio>
typedef long long ll;
using namespace std;
char c;
struct ff{
	int m[2][2];
};
void in(int &n)
{
	n=0;
	c=getchar();
	while(c>57||c<48)
	  c=getchar();
	do
	{
		n=n*10+c-48;
	    c=getchar();
	}
	while(c>=48&&c<=57);
}
ff mul(ff x,ff y,int p)
{
	ff kk;
	int i,j,k;
	for(i=0;i<2;i++)
	  for(j=0;j<2;j++)
	  {
	  	kk.m[i][j]=0;
	  	for(k=0;k<2;k++)
	  	  kk.m[i][j]=(kk.m[i][j]+(int)(((ll)x.m[i][k]*y.m[k][j])%p))%p;
	  }
	  return kk;
}
void fast_pow(ff s,int n,int p)
{
	static ff base;
	int i,j,k;
	for(i=0;i<2;i++)
	  for(j=0;j<2;j++)
	    if(i==j)
	      base.m[i][j]=1;
	    else
	      base.m[i][j]=0;
	while(n)
	{
		if(n&1)
		  base=mul(base,s,p);
		s=mul(s,s,p);
		n>>=1;
	}
	printf("%d\n",base.m[0][1]);
}
int main()
{
	freopen("eins.in","r",stdin);
	freopen("eins.out","w",stdout);
	int n,p,t;
	ff s;
	in(t);
	while(t--)
	{
	    in(n),in(p);
	    s.m[0][0]=s.m[0][1]=s.m[1][0]=1,s.m[1][1]=0;
		if(n==0)
		{
			printf("0\n");
			continue;
		}
		fast_pow(s,n,p);
	}
	return 0;
}