def main():
  import sys
  input=sys.stdin.readline

  import random

  def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


  for _ in range(int(input())):
    a,p=map(int,input().split())
    if isPrimeMR(p):print(1)
    else:print(-1)

if __name__ == "__main__":
  main()