#include #define be(v) (v).begin(),(v).end() #define pb(q) push_back(q) #define rep(i, n) for(int i=0;i> prime(ll n) { vector> v; ll m = n; for(ll i = 2; i * i <= n; i ++) { ll num = 0; while(m % i == 0) { num ++; m /= i; } if(num > 0) { v.push_back({i, num}); } } if(m > 1) v.push_back({m, 1}); return v; } long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } void solve() { ll n, m; cin >> n >> m; ll ans = 1; if(n >= m) { cout << 0 << endl; return; } if(n <= 300001) { for(ll i = 1; i <= n; i ++) { ans *= i; ans %= m; } cout << ans << endl; return; } for(auto [x, y] : prime(m)) { if(x == m) { ll num = m - 1; for(ll i = m - 1; i > n; i ++) { num *= i; num %= m; } cout << modinv(num, m) << endl; return; } cout << 0 << endl; return; } return ; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--) solve(); return 0; }