def Sieve_of_Eratosthenes(N,mode=False): """Nまでのエラトステネスの篩を実行 N:自然数 mode:False->素数のリスト,True->素数かどうかのリスト (False->[2,3,5,...],True->[False,False,True,True,False,True,...]) """ T=[True]*(N+1) T[0]=T[1]=0 a=2 while a*a<=N: if T[a]: b=a*a while b<=N: T[b]=False b+=a a+=1 if mode: return T else: return [k for k in range(N+1) if T[k]] #=========================================================== P_max=5*10**6 Prime_List=Sieve_of_Eratosthenes(P_max,True) T=int(input()) X=[0]*T for k in range(T): A,P=map(int,input().split()) if Prime_List[P]: if A%P: X[k]=1 else: X[k]=0 else: X[k]=-1 print("\n".join(map(str,X)))