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, \cdots, a_N~ (~1 \leq a_i \leq 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~.

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, \cdots, 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, \cdots, b_N~ thỏa mãn yêu cầu đề bài.

Sample Input 1

3
6 3 20

Sample Output 1

9 4 25

Sample Input 2

5
1 10 5 100 7

Sample Output 2

4 25 9 121 9

Notes

Ở test ví dụ thứ nhất:

• ~9~ là số nhỏ nhất không nhỏ hơn ~6~ có 3 ước nguyên dương là ~1, 3, 9~.

• ~4~ là số nhỏ nhất không nhỏ hơn ~3~ có 3 ước nguyên dương là ~1, 2, 4~.

• ~25~ là số nhỏ nhất không nhỏ hơn ~20~ có 3 ước nguyên dương là ~1, 5, 25~.