Description

程序细节：如何不超时！ 合理使用break； 尽量让循环少运算； 输出 从2 到n 之间 所有的素数。 如果n也是，也输出n。

Input Format

一个整数n n<=1000000

Output Format

多行数据，每行一个素数，从小到大顺序输出。

Sample

input

10

output

2
3
5
7

Hint

保证$n\leq 10^6$。

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

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