t = int(input())
#エラトステネスの篩で素数を列挙
x = [0]*(5*10**6+1)
for i in range(2,5*10**6+1):
  if x[i] == 0:
    I = i
    j = 2
    while I*j <= 5*10**6:
      x[I*j] = 1
      j += 1

for _ in range(t):
  a,p = map(int, input().split())
  if x[p] == 1:
    print(-1)
  else:
    #aがpの倍数なら当然答えは０
    if a%p == 0:
      print(0)
    else:
      #フェルマーの定理に注目
      print(1)