#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; ll powmod(ll a, ll k, ll mod){ ll ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=mod; } ap=ap*ap; ap%=mod; k>>=1; } return ans; } ll inv(ll a, ll mod){ return powmod(a, mod-2, mod); } ll solve(ll n, ll m){ if(n>=m || m==1) return 0; if(n==0) return 1%m; if(n<=1e6){ ll ret=1; for(ll i=1; i<=n; i++) (ret*=i)%=m; return ret; } for(ll i=2; i*i<=m; i++){ if(m%i==0) return 0; } ll ret=m-1; for(ll i=m-1; i>=n+1; i--){ (ret*=inv(i, m))%=m; } return ret; } int main() { int t; cin>>t; for(int i=0; i<t; i++){ ll n, m; cin>>n>>m; cout<<solve(n, m)<<endl; } return 0; }