import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { FastScanner sc = new FastScanner(System.in); PrintWriter pw = new PrintWriter(System.out); Sieve s = new Sieve((int)5e6); int t = sc.nextInt(); for(int i = 0; i < t; i++){ long p = sc.nextLong(); long a = sc.nextLong(); long pow = 1; for(long j = p; j > 1; j--){ pow *= j; pow %= (p-1); } pw.println(s.isPrime((int)p) ? rep2(a%p,pow,p) : -1); } pw.flush(); } private static long rep2(long b, long n, long mod){ if(n == 0) return 1; long bn = rep2(b,n/2,mod); if(n % 2 == 0){ return (bn*bn)%mod; }else{ return (bn*bn)%mod*b%mod; } } } class Sieve{ static int n; static int[] f; static ArrayList prime; public Sieve(int n){ long ln = n; prime = new ArrayList(); f = new int[n+1]; f[0] = f[1] = -1; for(int i = 2; i <= n; i++){ if(f[i] != 0){ continue; } f[i] = i; prime.add(i); long li = (long)i; for(long j = li*li; j <= ln; j += li){ if(f[(int)j] == 0){ f[(int)j] = i; } } } } public static boolean isPrime(int x){ return f[x] == x; } public static ArrayList factorList(int x){ ArrayList res = new ArrayList(); while(x != 1){ res.add(f[x]); x /= f[x]; } return res; } public static HashMap factor(int x){ ArrayList fl = factorList(x); HashMap res = new HashMap(); if(fl.size()==0){ return new HashMap(); } int prev = fl.get(0); int cnt = 0; for(int p : fl){ if(prev == p){ cnt++; }else{ res.put(prev,cnt); prev = p; cnt = 1; } } res.put(prev,cnt); return res; } } class FastScanner { private BufferedReader reader = null; private StringTokenizer tokenizer = null; public FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } public String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } public double nextDouble() { return Double.parseDouble(next()); } public String[] nextArray(int n) { String[] a = new String[n]; for (int i = 0; i < n; i++) a[i] = next(); return a; } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } public long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } }