Ozi is a topnotch chocolate gourmet and he tastes as many chocolates as he can during a day. However, Mustif, who loves him so much, thinks that it would be harmful to him to consume so much chocolate and puts a limit on the number of chocolates Ozi can taste for each day. Since Ozi loves math and prime numbers, he decides that the number of chocolates he will taste to be the biggest prime number possible.

Can you find how many chocolates Ozi can taste in the \(N\) days?

Input

The initial line only includes \(\mathbf{N}\), which stands for the total number of days.

In the next line, there is the list \(\mathbf{A}\) which consists of \(\mathbf{N}\) integers. Every \(\mathbf{A_{i}}\), indicates the limit of the chocolate number Ozi can taste in \(\mathbf{i}\)'th day.

• \(1 \leq \mathbf{N} \leq 10^{5}\)
• \(2 \leq \mathbf{A_{i}} \leq 10^{6}\)

Output

In a single line, for each day, how many chocolates Ozi will taste will be printed.

Examples

Input:

4
4 7 44 77

Output:

3 7 43 73

Input:

4
47 74 474 747

Output:

47 73 467 743