```
#include<bits/stdc++.h>
using namespace std;
int a[11]={0,1,2,4,8,16,32,64,128,256,512};
long long n,q;
long long ans;
int t;
long long mul(long long a,long long n,long long b)
{
long long ans=0;
a=a%b;
while(n>0)
{
if(n%2==1)
ans=(ans+a)%b;
n=n/2;
a=(a+a)%b;
}
return ans;
}
long long pow(long long a,long long n,long long b)
{
long long ans=1;
a=a%b;
while(n>0)
{
if(n%2==1)
ans=mul(ans,a,b);
n=n/2;
a=mul(a,a,b);
}
return ans;
}
int main()
{
//freopen("jian.in","r",stdin);
//freopen("jian.out","w",stdout);
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&n,&q);
if(n<=10){
printf("%d\n",a[n]%q);
}
else {
printf("%lld\n",pow(2,n-1,q));
}
}
}
```