MX_P=5000000
isprime=[True]*(MX_P+1)
isprime[0]=isprime[1]=False
for n in range(2,MX_P+1):
    if isprime[n]:
        s=2*n
        while s<=MX_P:
            isprime[s]=False
            s+=n
T=int(input())
for _ in range(T):
    A,P=map(int,input().split())
    if isprime[P]:
        print(0 if A%P==0 else 1)
    else:
        print(-1)