cnt_num = int(input())
dataset = [int(input()) for i in range(cnt_num)]

for i in dataset:
    if i <= 1:
        continue
    if i == 2:
        print(i)
        continue
    if i % 2 == 0:
        continue

    ok = ''
    for j in range(3,i,2):
        if i % j == 0:
           break
        else:
           ok = 'X'
           break

    if ok == 'X':
        print(i)
        continue