Sieve of Eratosthenes

The Calder Cipher Club runs an evening workshop where each attendee picks a prime number off a printed sheet. The organiser types an upper limit into the sheet generator beforehand, and wants every prime from 2 up to that limit -- the complete list, in increasing order, not a sample. The limit changes from week to week, and on the introductory night it is set so low that there are no primes in range at all.

Task: Print every prime from 2 to n inclusive, found with the Sieve of Eratosthenes -- that is, by crossing off multiples rather than testing each number on its own.

Input

A single line holding one integer n, with 1 <= n <= 1,000,000.

Output

One line holding the primes in increasing order, separated by single spaces. When no prime is in range, that line is empty.

Example:

Input:
20

Output:
2 3 5 7 11 13 17 19