mod = 1000000007 eps = 10**-9 def main(): import sys input = sys.stdin.buffer.readline N0 = 5*10**6 is_prime = [1] * (N0+1) is_prime[0] = is_prime[1] = 0 for i in range(2, N0+1): if is_prime[i] == 0: continue for j in range(2, N0+1): if i*j > N0: break is_prime[i*j] = 0 for _ in range(int(input())): a, p = map(int, input().split()) if is_prime[p]: print(1) else: print(-1) if __name__ == '__main__': main()