import math


def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True
  
T = int(input())
for _ in range(T):
    A, P = map(int, input().split())
    if isPrime(P):
        print(1 if A % P else 0)
    else:
        print(-1)