t=5000001
A=[1 for i in range(t)]
for i in range(2,t):
    if A[i]:
        for j in range(2*i,t,i):
            A[j]=0
N=int(input())
for i in range(N):
    print(1 if A[list(map(int,input().split()))[1]] else -1)