#yuki1140
def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

l=get_primes(p+1)
t=int(input())
for i in range(t):
 a,p=map(int,input().split())
 if p in l:
  print(1 if a%p else 0)
 else:
  print(-1)