Problem: Twin Prime Conjecture

Want to try solving this problem? You can submit your code online if you log in or register.

Twin Prime Conjecture

Input File: primein.txt
Output File: primeout.txt
Time Limit: 0.1 seconds

A prime number is any integer greater than 1 whose only positive divisors are 1 and itself. For example, 13 is a prime number, because its only divisors are 1 and 13. 15 is not a prime number, because its divisors are 1, 3, 5 and 15.

The twin prime conjecture is a famous unsolved mathematical problem about prime numbers. It says, "There are infinitely many pairs of primes which are 2 apart." Another interesting problem is the easier prime conjecture, which says: "It is possible to write a program that takes in some number N as input, and outputs all the prime numbers between 1 and N."

Your task here is to prove the easier prime conjecture by writing a program that takes in some number N as input and outputs all the prime numbers between 1 and N.

Input

The input file will consist of a single integer N, 2 <= N <= 500,000.

Output

Your output file should consist of all the primes between 1 and N inclusive, separated by line breaks. They should be given in increasing order.

Sample Input

Sample Output

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.