import java.io.*; import java.util.*; import java.math.BigInteger; class Main { static long powerMod(long x, long exponent, long MOD) { long prod = 1; for (int i = 63; i >= 0; --i) { prod = (prod * prod) % MOD; if ((exponent & 1L << i) != 0) { prod = (prod * x) % MOD; } } return prod; } static long f(long n,long m){ if(n>=m)return 0; long ret=-1; if(m<=310000){ // brute long ans=1; for(long i=1;i<=n;++i)ans=ans*i%m; ret=ans; return ret; //System.err.println("brute="+ans); } boolean pr=BigInteger.valueOf(m).isProbablePrime(20); if(pr){ // Wilson's theorem long ans=m-1; for(long i=m-1;i>n;--i){ ans=ans*i%m; } ret=powerMod(ans,m-2,m); return ret; // System.err.println("wilson="+ret); }else if(m!=4&&2*m<3*n){ // System.err.println("nt=0"); ret=0; } return ret; } public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); int t=sc.nextInt(); while(t-->0){ long n=sc.nextLong(); long m=sc.nextLong(); out.println(f(n,m)); } out.close(); } // http://codeforces.com/blog/entry/7018 //-----------PrintWriter for faster output--------------------------------- public static PrintWriter out; //-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } int[] nextIntArray(int n){ int[]r=new int[n]; for(int i=0;i