Generate all prime numbers up to n

As you can now check for the primality of any number, you are now asked to check if the number is prime for all the numbers up to n and print all the prime ones.

Input

The first line of the input contains a single integer n (2 ≀ n ≀ ).

Output

The program should print all the prime numbers smaller than or equal to n.

Examples

Input
Output
8
2 3 5 7
17
2 3 5 7 11 13 17
19
2 3 5 7 11 13 17 19
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue