Gọi một số tự nhiên có đúng hai ước dương là số có hai ước (tức là số nguyên tố). Huy có một dãy ~A~ gồm ~N~ số nguyên dương. Vì chỉ thích các số có đúng hai ước nên Huy thay đổi các phần tử trong dãy ~A~ như sau: với mỗi phần tử ~A_i~, nếu ~A_i~ có nhiều hơn hai ước, Huy lặp lại thao tác giảm ~A_i := A_i - 1~ cho đến khi ~A_i~ có đúng hai ước. Hãy in ra dãy ~A~ sau khi Huy thay đổi.

Yêu cầu

Cho ~N~ và dãy ~A~, hãy biến đổi mỗi ~A_i~ về số nguyên tố lớn nhất không vượt quá ~A_i~ (nếu ~A_i~ đã là nguyên tố thì giữ nguyên). In ra dãy sau cùng.

Dữ liệu

• Dòng 1: số nguyên dương ~N~.
• Dòng 2: ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~.

Kết quả

In ra dãy sau khi thay đổi, các số cách nhau một dấu cách.

Ví dụ

Ví dụ

Input

3
2 9 16

Output

2 7 13

Giải thích

• Phần tử ~2~ đã là số có hai ước (nguyên tố) nên giữ nguyên.
• ~9 \to 8 \to 7~ (dừng ở ~7~ vì đã có hai ước).
• ~16 \to 15 \to 14 \to 13~ (dừng ở ~13~).

Chấm điểm

• 60% số điểm: ~2 \le ~N~, ~A_i~ \le 2000~.
• 20% số điểm: ~2 \le ~N~, ~A_i~ \le 20000~.
• 20% số điểm: ~2 \le ~N~, ~A_i~ \le 2{,}000{,}000~.

$$ \text{Gợi ý kiểm tra nguyên tố hiệu quả: sàng Eratosthenes tới } \max A_i \text{ và tra ngược mỗi } A_i. $$