import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
n=10**7
sieve=[-1]*(n+1)
for i in range(2,n+1):
  if sieve[i]==-1:
    sieve[i]=i
    for j in range(i*i,n+1,i):
      if sieve[j]==-1:
        sieve[j]=i
for _ in range(t):
	a,p=map(int,input().split())
	if sieve[p]==p:
		if a%p==0:
			print(0)
		else:
			print(1)
	else:
		print(-1)