import sys
input=sys.stdin.readline
prime=[1]*5000001
prime[0]=prime[1]=0
for i in range(2,5000001):
  if prime[i]:
    for j in range(i+i,5000001,i):prime[j]=0
for _ in range(int(input())):
  a,p=map(int,input().split())
  if prime[p]:
    if a%p:print(1)
    else:print(0)
  else:print(-1)