Flowright has registered in a bread eating contest, in which he will be competing against $N$ $(1\le N\le 500000)$ competitors for the grand prize of a toaster! To win, he must eat more slices of bread than all the other competitors at the tournament. Being a contrarian individual, Flowright wishes to lose against each competitor. Flowright has confidence in his abilities, but he also has a strange compulsion to eat a prime number of bread slices in each round.

Wanting to know his chances of losing, Flowright has determined $C_i$ $(1\le C_i\le {10}^4)$, the number of slices that his competitors can eat per round. As Flowright is very hungry, help him determine the maximum number of slices he can eat in each round while still losing to his competitors.

Note: For 50% of points, $N\le {10}^5$ and $C_i\le {10}^3$.

Input Specification

On the first line, one integer $N$ representing the number of competitors.

On the second line, $N$ space separated integers $C_i$, representing the amount of bread that the $i^{th}$ competitor can eat.

Output Specification

Output $N$ lines, with the $i^{th}$ line representing the largest number of bread slices Flowright can eat while still losing against the $i^{th}$ competitor. If there is no way that Flowright can lose the round, output no can do.

Sample Input

3
5 7 1

Sample Output

3
5
no can do

Explanation of Sample Output

In the first two rounds, Flowright can eat 3 and 5 slices respectively. In the third round, there is no valid number of slices that Flowright can eat and still lose.