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\). Với mỗi \(a_i\) cần xác định số đặc biệt \(b_i\) nhỏ nhất không nhỏ hơn \(a_i\).

Input:

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 \leq N \leq 10^6)\).
• Dòng thứ hai gồm \(N\) sô nguyên \(a_1,a_2,...,a_N (1\leq a_i \leq 10^9)\).

Output:

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\) thoả mãn yêu cầu đề bài.

Example

3
6 3 20

9 4 25

5
1 10 5 100 7

4 25 9 121 9