n = int(input()) while True: try: num = int(input()) if num in [2, 3]: print('true') continue for j in range(2, int(num ** 0.5) + 1): if num % j == 0: print('false') break if j == int(num ** 0.5): print('true') except: break