#yuki1140
prime=[1]*5000001
for i in range(2,5000001):
 if prime[i]:
  for j in range(i**2,5000001,i):
   prime[j]=0
x=int(input())
for i in range(x):
 a,p=map(int,input().split())
 if prime[p]:
  print(1 if a%p else 0)
 else:
  print(-1)