#include<bits/stdc++.h> #define int long long using namespace std; int T,n,p; void read(int &x){ x=0; bool f=0; char c=getchar(); while(!isdigit(c)){ if(c=='-')f=1; c=getchar(); } while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); } if(f)x=-x; return; } int ans[]={0,0,0,0,2,30,326,3234,31762,321294,3422702,38879082,473708154}; void slv(){ read(n),read(p); cout<<ans[n]%p<<endl; } signed main(){ //freopen("sort.in","r",stdin); // freopen("sort.out","w",stdout); read(T); while(T--)slv(); return 0; }