n,m;long long a,b;main(t){for(scanf("%b",&t);t--;a=0){scanf("%b%b",&n,&m);for(b=1;b*++b<=m;)if(m%b<1){if(n<b+m/b)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);}}