Bài toán: Số đặc biệt

Bờm đang học về số học, cậu rất yêu thích những con số có tính chất đặc biệt. Số đặc biệt là số có đúng 3 ước nguyên dương.

Yêu cầu:
Cho N số nguyên dương lần lượt là ~a_1, a_2, ..., a_N~ ~(1 ≤ a_i ≤ 10^9)~. Với mỗi số ~a_i~, cần xác định số đặc biệt ~b_i~ nhỏ nhất không nhỏ hơn ~a_i~.

Dữ liệu vào:

Từ tệp văn bản SDB.INP gồm 2 dòng:

• Dòng thứ nhất chứa một số N (1 ≤ N ≤ ~10^6~).
• Dòng thứ hai gồm N số nguyên ~a_1, a_2, ..., a_N~ ~(1 ≤ a_i ≤ 10^9)~.

Kết quả:

Đưa ra tệp văn bản SDB.OUT gồm N số nguyên ~b_1, b_2, ..., b_N~ thỏa mãn yêu cầu đề bài.

Ví dụ: