说明

我们将一个正整数分解质因数，即分解成若干个质数的乘积，若得到的质因数的个数为素数个(素数即质数)，则我们称这个整数为幸运数。例如12=223，它有3个质因数，分别是2、2、3，而3为素数，所以12是一个幸运数；相反210不是一个幸运数，因为210=235*7，它有4个质因数，分别是2、3、5、7，而4不是素数。现在我们要求出不大于n的所有幸运数(2<=n<=100000)。

输入格式

仅有一行包含一个整数n。

输出格式

若干行，每行一个幸运数。要求按从小到大的顺序输出。

样例

12

4
6
8
9
10
12

提示

提示：

4=2*2（2个质因数）

6=2*3（2个质因数）

8=222（3个质因数）

9=3*3（2个质因数）

10=2*5（2个质因数）

12=223（3个质因数）

数据规模：

对于50%的数据，n<=1000；

对于80%的数据，n<=10000；

对于100%的数据，n<=100000。