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

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

All the elements of ~a~ are distinct.

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~.

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.

## Comments