Background

Special for beginners, ^_^

Description

桐桐在学完了上节课的知识后，对信息学越发感兴趣了。桐桐是一个很善于思考的学生，她发现上节课中例题的n 最大是40000,如果数据再大一些，比如n=10^7，那么判断素数的算法能否在1秒内给出答案呢？桐桐用程序实际测试 的时间超过了 1秒，你能帮助桐桐解决这个难题吗?即:在1秒的时间内输出不大$n(1<n≤10^7)$的所有素数。

Format

Input

一个正整数n(1<n≤10^7)。

Output

输出不大于n的所有素数，每行输出5个素数,每个数字后面接一个空格

Samples

10

2 3 5 7 

Limitation

1s, 1024KiB for each test case.