记录编号	128900	评测结果	AAAAAAAAAA
题目名称	1426.eins	最终得分	100
用户昵称	东方老败	是否通过	通过
代码语言	Pascal	运行时间	4.914 s
提交时间	2014-10-18 19:03:51	内存使用	0.17 MiB

type zhen=array[0..1,0..1]of int64;
     jie=array[0..1]of int64;
const z:zhen=((0,1),(1,1));
var n,p,t:int64;
    f,g:jie;
    c,o,u,v:zhen;
	i,j,k:longint;

procedure cheng(x:jie;y:zhen);
var i,j,k:longint;u:jie;
begin
 f[0]:=(x[0]*y[0,0]+x[1]*y[1,0])mod p;
 f[1]:=(x[0]*y[0,1]+x[1]*y[1,1])mod p;
end;

procedure work;
var i,j,k:longint;
begin
 readln(n,p);
 if n=0 then begin writeln(0);exit;end;
 n:=n-1;
 k:=1;c:=z;
 while N>0 do
 begin
  if n and 1<>0 then cheng(f,c);

  u[0,0]:=(c[0,0]*c[0,0]+c[0,1]*c[1,0])mod p;
  u[0,1]:=(c[0,0]*c[0,1]+c[0,1]*c[1,1])mod p;
  u[1,0]:=(c[1,0]*c[0,0]+c[1,1]*c[0,1])mod p;
  u[1,1]:=(c[1,0]*c[0,1]+c[1,1]*c[1,1])mod p;
  c:=u;

 n:=n>>1;
 end;

writeln(f[1] mod p);
end;

begin
 assign(input,'eins.in');reset(input);
 assign(output,'eins.out');rewrite(output);
 readln(t);
 for i:=1 to t do
 begin
  f[0]:=0;f[1]:=1;
  work;
  end;
  close(output);
end.