n,m,d;long long a,b;main(t){for(scanf("%d",&t);t--;a=0){scanf("%d%d",&n,&m);for(d=1;d*++d<=m;)if(m%d<1){if(n<d+m/d)for(a=1;n;)a=a*n--%m;goto l;}if(n<m){for(b=1;++n<m;)b=b*n%m;for(a=m-1,n-=2;n;n/=2,b=b*b%m)if(n&1)a=a*b%m;}l:printf("%lld\n",a);}}