import sys
S=sys.stdin.readlines()
T=int(S[0])
A,P=0,0
PR=[1]*6000000
PR[0]=0
PR[1]=0
for i in range(2,6000000):
  if PR[i]:
    for j in range(i*2,6000000,i):
      PR[j]=0
for i in range(T):
  A,P=map(int,S[i+1].split())
  if PR[P] and A%P:
    print(1)
  elif PR[P]:
    print(0)
  else:
    print(-1)