题目描述

把一个正整数分解为若干质数的乘积，如果质因子的个数也是质数，则称它为幸运数。重复质因子重复计数，例如 $12=2\times2\times3$ 有 $3$ 个质因子，所以是幸运数。输出不超过 $n$ 的所有幸运数。

输入格式

一行一个整数 $n$。

输出格式

从小到大输出，每行一个幸运数。没有幸运数时输出为空。

样例

12

4
6
8
9
10
12

数据范围

对于 $50\%$ 的数据，$n\le1000$；对于 $80\%$ 的数据，$n\le10000$；对于 $100\%$ 的数据，$2\le n\le100000$。