""" https://yukicoder.me/problems/no/1140 """ from sys import stdin import math def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる ret = [] divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1) flag = [True] * (n+1) flag[0] = False flag[1] = False ind = 2 while ind <= n: if flag[ind]: ret.append(ind) ind2 = ind ** 2 while ind2 <= n: flag[ind2] = False divlis[ind2] = ind ind2 += ind ind += 1 return ret,divlis plis,divlis = Sieve(6000000) pset = set(plis) TT = int(stdin.readline()) ANS = [] for _ in range(TT): A,P = map(int,stdin.readline().split()) if P not in pset: ANS.append(-1) elif A % P == 0: ANS.append(0) else: ANS.append(1) print (*ANS,sep="\n")