def make_primes(n: int) -> list[int]:
    ps = [2]
    t = [True] * (n + 1)
    for i in range(3, n+1, 2):
        if t[i]:
            ps.append(i)
            for j in range(i+i, n+1, i):
                t[j] = False
    return ps


pset = set(make_primes(5_000_000))


def solve(a, p):
    if p in pset:
        if a % p == 0:
            return 0
        return 1

    return -1


T = int(input())
for _ in range(T):
    A, P = map(int, input().split())
    ans = solve(A, P)
    print(ans)