import math
import random
import math
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
from sys import stdin
Q = get_sieve_of_eratosthenes(5000001)
#print(Q[0])
Q = set(Q)
t = int(input())
for i in range(t):
  a,p = map(int,stdin.readline().rstrip().split())
  if p in Q:
    if a % p == 0:
      print(0)
    else:
      print(1)
  else:
    print(-1)