import sys
import math


def input(): return sys.stdin.readline().rstrip('\n')


def main():
    s = [True] * (5 * 10 ** 6 + 1)
    s[0] = s[1] = False
    for i in range(2, math.isqrt(len(s) - 1) + 1):
        if s[i]:
            for j in range(i * i, len(s), i):
                s[j] = False

    t = int(input())
    for _ in range(t):
        a, p = map(int, input().split())
        if s[p]:
            print(1 if a % p != 0 else 0)
        else:
            print(-1)


if __name__ == '__main__':
    ret = main()
    if ret is not None:
        print(ret)