def primes(n): is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n**0.5) + 1): if not is_prime[i]: continue for j in range(i * 2, n + 1, i): is_prime[j] = False l = [False]*(n+1) for i in range(n+1): if is_prime[i]: l[i] = True return l N = 5*(10**6)+1 E = primes(N) T = int(input()) for _ in range(T): A,P = map(int,input().split()) if E[P]: if A%P != 0: print(1) else: print(0) else: print(-1)