def eratos(n): primes = list(range(n+1)) primes[0] = -1 primes[1] = -1 for i in range(2, int(n**0.5) + 1): if primes[i] != i: continue for j in range(i*i, n+1, i): if primes[j] == j: primes[j] = i return primes prime_table = eratos(5*10**6) t = int(input()) ans = [] for _ in range(t): a, p = map(int, input().split()) if prime_table[p] != p: ans.append(-1) else: if a % p == 0: ans.append(0) else: ans.append(1) for i in ans: print(i)