Minimum Divisible Sequence
Limits: 2 sec., 512 MiB
You are given an integer n.
Construct an integer sequence a of length m satisfying the following conditions.
1≤ai≤n for all 1≤i≤m.
For each 1≤k≤n, there exists 1≤i≤m such that ai is a multiple of k.
The length m is minimum possible.
Input
The single line contains an integer n.
Output
In the first line print an integer m – the length of the sequence a.
In the second line print m integers ai – the elements of the sequence.
If there are multiple answers, any of them will be accepted.
Constraints
1≤n≤105.
Samples
Input (stdin) | Output (stdout) |
---|---|
7 | 4 4 7 5 6 |
Notes
In the example, one of the possible sequences is a=(4,7,5,6).
a1=4 is a multiple of 1.
a1=4 is a multiple of 2.
a4=6 is a multiple of 3.
a1=4 is a multiple of 4.
a3=5 is a multiple of 5.
a4=6 is a multiple of 6.
a2=7 is a multiple of 7.
It is impossible to construct a sequence satisfying the conditions of length less than four.