Trong khi học về số học, Nam tình cờ phát hiện ra một loại số có tính chất đặc biệt.
Một số nguyên dương được gọi là số đặc biệt nếu nó có chính xác 3 ước nguyên dương.

Ví dụ:

• Số 4 có 3 ước nguyên dương là 1, 2, 4 nên là số đặc biệt.
• Số 6 có 4 ước nguyên dương là 1, 2, 3, 6 nên không phải số đặc biệt.

Yêu cầu

Cho một dãy gồm N số nguyên dương ~a_1, a_2, \dots, a_N~.
Với mỗi số ~a_i~, hãy tìm số đặc biệt nhỏ nhất ~b_i~ sao cho ~b_i ≥ a_i~.

Dữ liệu vào (Input)

• Dòng 1: một số nguyên dương ~N (1 ≤ N ≤ 10^6)~ – số lượng phần tử của dãy.
• Dòng 2: N số nguyên dương ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~ cách nhau bởi một khoảng trắng.

Kết quả (Output)

• In ra một dòng duy nhất gồm N số nguyên ~b_1, b_2, \dots, b_N~ thỏa mãn yêu cầu, các số cách nhau bởi đúng một khoảng trắng.

Ví dụ

Input 1

3
6 3 20

Output 1

9 4 25

Input 2

5
1 10 5 100 7

Output 2

4 25 9 121 9