#!/usr/bin/env python3

import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

def is_prime(n):
    if n <= 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


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