Nếu có số tự nhiên ~x~ chia hết cho số tự nhiên ~y~ thì ta nói ~y~ là ước số của ~x~. Ví dụ: ~1, 2, 3, 12~ là ước của ~12~; còn ~5, 8~ thì không phải là ước của ~12~.

Huy có một danh sách gồm ~N~ số nguyên dương ~A[1],A[2],...,A[N]~. Huy đặc biệt thích các số tự nhiên có đúng hai ước nên sẽ thay đổi các phần tử thuộc dãy ~A~ nếu chúng có nhiều hơn hai ước. Với mỗi phần tử ~A[i]~ (~1 \leq i \leq N~) có nhiều hơn hai ước Huy sẽ lặp lại việc thay đổi ~A[i]=A[i]-1~ cho đến khi ~A[i]~ có đúng hai ước.

Yêu cầu: Cho ~N~ và dãy ~A~, hãy in ra dãy ~A~ sau khi Huy thay đổi.

Input

Vào từ file văn bản HAIUOC.INP:

• Dòng đầu tiên là số nguyên dương ~N~;
• Dòng thứ hai lần lượt là ~N~ số nguyên dương ~A[1],A[2],...,A[N]~.

Output

Vào từ file văn bản HAIUOC.OUT là dãy ~A~ sau khi thay đổi. Các số viết cách nhau một dấu cách.

Scoring

• Subtask ~1~ ~(60\%)~: ~2 \leq N,A[i] \leq 2000~;
• Subtask ~2~ ~(20\%)~: ~2 \leq N,A[i] \leq 20000~;
• Subtask ~3~ ~(20\%)~: ~2 \leq N,A[i] \leq 2000000~.

Example input 1

3
2 9 16

Example output 1

2 7 13