class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        for i in range(2, self.N+1):
            if i in self.prime:
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.prime.remove(j)

    def show_primes(self):
        return self.prime


Prime_table = Primes(5*10**6).show_primes()
T = int(input())
que = [tuple(map(int, input().split())) for i in range(T)]
for A, P in que:
    if A in Prime_table:
        if A % P == 0:
            print(0)
        else:
            print(1)
    else:
        print(-1)