import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines def sieve(n): if( n <= 1): return [] elif(n==2): return [2] primes = [2] len_list = (n+1)//2 len_sqrt = int(len_list**0.5) + 1 flags = [True] * len_list flags[0] = False for i in range(len_sqrt): if(flags[i]): start = ((i*2+1)**2)//2 for j in range( start, len_list, i*2+1): flags[j] = False return [2] + [i*2+1 for i in range(len_list) if flags[i]] t = int(readline()) data = list(map(int,read().split())) primes = sieve(5*10**6) nums = [-1]*(5*10**6) for pi in primes: nums[pi]=1 ans = [] it = iter(data) for a,p in zip(it,it): if(nums[p]==-1): ans.append(-1) else: ans.append(1*(a%p > 0)) print('\n'.join(map(str,ans)))