Description

我们将一个正整数分解质因数，即分解成若干个质数的乘积，若得到的质因数的个数为素数个(素数即质数)，则我们称这个整数为幸运数。

例如12=2*2*3，它有3个质因数，分别是2、2、3，而3为素数，所以12是一个幸运数；

相反210不是一个幸运数，因为210=2*3*5*7，它有4个质因数，分别是2、3、5、7，而4不是素数。现在我们要求出不大于n的所有幸运数

Input Format

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

Output Format

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

12

4
6
8
9
10
12

Hint

【样例解释】

4=2*2 有2个质因数 是幸运数

5=5 有1个质因数 不是幸运数

6=2*3 有2个质因数 是幸运数

7=7 有1个质因数 不是幸运数

8=2*2*2 有3个质因数 是幸运数

9=3*3 有2个质因数 是幸运数

10=5*2 有2个质因数 是幸运数

11=11 有1个质因数 不是幸运数

12=2*2*3 有3个质因数 是幸运数

【数据范围约定】

对于50%的数据，保证4<= n <=1000

对于80%的数据，保证4<= n <=10000

对于100%的数据，保证4<= n <=100000

Source