#yuki1140
T=int(input())
limit = 5000000
is_prime=[True]*500001
is_prime[0]=is_prime[1]=False

for p in range(0,500001):
 if not is_prime[p]:
  continue
 for i in range(p*p,500001,p):
  is_prime[i]=False


for i in range(T):
 A,P = map(int, input().split())
 if is_prime[P]:
  if A % P == 0:
   print(0)
  else:
   print(1)
 else:
  print(-1)