import sys
def sieve(n):
  is_prime = [True for _ in range(n+1)]
  is_prime[0] = False
  for i in range(2, n+1):
    if is_prime[i-1]:
      j = 2 * i
      while j <= n:
        is_prime[j-1] = False
        j += i
  return is_prime
def solve():
  input = sys.stdin.readline
  is_prime = sieve(5*10**6)
  T = int(input())
  ans = [-1]*T
  for i in range(T):
    A,P = map(int, input().split())
    if is_prime[P-1]:
      if A%P==0:
        ans[i] = 0
      else:
        ans[i] = 1
  return ans
print(*solve(),sep='\n')