You have an array $$$a_0, a_1, \ldots, a_{n-1}$$$ of length $$$n$$$. Initially, $$$a_i = 2^i$$$ for all $$$0 \le i \lt n$$$. Note that array $$$a$$$ is zero-indexed.

You want to reverse this array (that is, make $$$a_i$$$ equal to $$$2^{n-1-i}$$$ for all $$$0 \le i \lt n$$$). To do this, you can perform the following operation no more than $$$250\,000$$$ times:

Select an integer $$$i$$$ ($$$0 \le i \lt n$$$) and replace $$$a_i$$$ by $$$a_i \oplus a_{(i+1)\bmod n}$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to find any sequence of operations that will result in the array $$$a$$$ being reversed. It can be shown that under the given constraints, a solution always exists.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the length of the array $$$a$$$.

Output

On the first line print one integer $$$k$$$ ($$$0 \le k \le 250\,000$$$) — the number of operations performed.

On the second line print $$$k$$$ integers $$$i_1,i_2,\ldots,i_k$$$ ($$$0 \le i_j \lt n$$$). Here, $$$i_j$$$ should be the integer selected on the $$$j$$$-th operation.

Note that you don't need to minimize the number of operations.

Note

In the notes, the elements on which the operations are performed are colored red.

In the first test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]$$$.

In the second test case, array $$$a$$$ will change in the following way:

$$$[1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,2,1]$$$.

Circular Xor Reversal

Examples