codevs 1250

 1 #include<bits/stdc++.h>
 2 #define inc(i,l,r) for(i=l;i<=r;i++)
 3 #define dec(i,l,r) for(i=l;i>=r;i--)
 4 #define mem(a) memset(a,0,sizeof(a))
 5 #define ll long long
 6 #define succ(x) (1<<x)
 7 #define NM 3
 8 using namespace std;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
12     while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
13     return x*f;
14 }
15 struct matrix{
16     int n,m,a[NM][NM];
17 }a,b,tmp;
18 int n,m,T,inf;
19 matrix operator*(const matrix&x,const matrix&y){
20     matrix s;
21     int i,j,k;
22     inc(i,1,x.n)
23     inc(j,1,y.m){
24         s.a[i][j]=0;
25         inc(k,1,x.m)
26         (s.a[i][j]+=x.a[i][k]*y.a[k][j])%=inf;
27     }
28     s.n=x.n;s.m=y.m;
29     return s;
30 }
31 matrix mul(int k){
32     matrix s=a,t=a;
33     k--;
34     while(k>0){
35         if(k%2)s=s*t;
36         t=t*t;k/=2;
37     }
38     return s;
39 }
40 int main(){
41     T=read();
42     a.n=a.m=2;a.a[1][1]=0;a.a[1][2]=a.a[2][1]=a.a[2][2]=1;
43     b.n=2;b.m=1;
44     while(T--){
45         n=read();inf=read();
46         if(n<=1){
47             printf("%d\n",1%inf);
48             continue;
49         }
50         tmp=mul(n-1);
51         b.a[1][1]=b.a[2][1]=1;
52         b=tmp*b;
53         printf("%d\n",b.a[2][1]);
54     }
55     return 0;
56 }