#yuki1140
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)