You are given an integer ~n~. Construct an array ~a~ of positive integers satisfying the following requirements:

1. The elements of ~a~ do not exceed ~n + 1~.

2. All the elements of ~a~ are distinct.

3. For each ~x~ from ~2~ to ~n~, there exists a pair of indices ~(i, j)~ such that ~i \neq j~ and ~a_i \equiv a_j \pmod x~.

4. The length of ~a~ is as small as possible.

Input

The input contains a single integer ~n~ (~2 \le n \le 10^5~).

Output

In the first line, output a single integer ~k~ – the length of the constructed array ~a~.

In the second line, output ~k~ integers ~a_1, a_2, \ldots, a_k~. The array must satisfy all requirements in the statement.

If there are multiple possible answers, output any.

Scoring

• Subtask 1 (~10~ points): ~n \le 16~.

• Subtask 2 (~90~ points): No additional constraints

The total score for this problem is ~100~.

Sample Input 1

5

Sample Output 1

4
1 3 5 6

Notes

It can be easily seen that the array ~[1, 3, 5, 6]~ satisfies the first two requirements. We show that it satisfies the third requirement as well:

• The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 2~.

• The pair of values ~3~ and ~6~ are both divisible by ~x = 3~.

• The pair of values ~1~ and ~5~ both has remainder ~1~ when divided by ~x = 4~.

• The pair of values ~1~ and ~6~ both has remainder ~1~ when divided by ~x = 5~.

It can be shown that, for ~n = 5~, there exists no array ~a~ with length less than ~4~ satisfying all requirements.