P = list(range(5*10**6))
for i in range(2,5*10**6):
    if i*i>5*10**6:break
    for j in range(i*i,5*10**6,i):
        P[j] = P[i]
Q = set()
for i in range(2,5*10**6):
    if P[i]==i:
        Q.add(i)
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
T = int(input())
for _ in range(T):
    a,p = map(int,input().split())
    if p not in Q:
        print(-1)
    else:
        if a==1:
            print(1)
        else:
            d = gcd(a,p)
            if d==p:
                print(0)
            else:
                print(1)