Program CODEVS1250;type  arr=array[1..2,1..2] of longint;var T,n,mo:longint;    a,b:arr;operator *(a,b:arr) c:arr;var i,j,k,sum:longint;begin  fillchar(c,sizeof(c),0);  for i:=1 to 2 do    for j:=1 to 2 do      begin        sum:=0;        for k:=1 to 2 do          sum:=(sum+a[i,k]*b[k,j]) mod mo;        c[i,j]:=sum;      end;  exit(c);end;procedure main;var i,j:longint;begin  readln(n,mo);  a[1,1]:=1; a[1,2]:=0; a[2,1]:=0; a[2,2]:=1;  b[1,1]:=0; b[1,2]:=1; b[2,1]:=1; b[2,2]:=1;  while n>0 do    begin      if n mod 2=1 then a:=a*b;      n:=n div 2;          b:=b*b;        end;  writeln((a[1,1]+a[1,2]) mod mo);end;begin  readln(T);  while T>0 do begin dec(T); main; end;end.