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},\ \ldots,\ 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}\).

Dữ liệu vào:

+ 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},\ \ldots,\ a_{n}\ (1 \leq a_{i} \leq 10^{9})\).

Kết quả: Đưa ra gồm \(n\) số nguyên \(b_{1},\ b_{2},\ \ldots,\ b_{n}\) thỏa mãn yêu cầu đề bài.

Ví dụ: