题目描述

​ 将一个正整数分解质因数，即分解成若干质数的乘积，若得到的质因数的个数也是质数，则称这个整数为“幸运数”。例如12=2x2x3，它有3个质因数,分别是2、2、3,而3为质数，所以12是一个幸运数。210不是一个幸运数,因为210=2x3x5x7,它有4个质因数，分别是2、3、5、7，而4不是质数。 编程求出不大于n的所有幸运数。

输入格式

​ 一行一个正整数n,2≤n≤100000。

输出格式

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

样例数据

input

12

output

4
6
8
9
10
12

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$256 \text{MB}$