I. Amidakuji
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a positive integer $$$N$$$. Construct a sequence of permutations of $$$(1,2,\cdots,N)$$$, $$$p_1,p_2,\ldots,p_K$$$, that satisfy following conditions, or report that it's impossible.

  • $$$0 \leq K \leq \lceil \log_2 N \rceil + 1$$$, where $$$K$$$ is the length of the sequence.
  • $$$p_1,p_2,\ldots,p_K$$$ are permutations of $$$(1,2,\ldots,N)$$$. In other words, they are bijections from $$$\{1,2,\ldots,N\}$$$ to $$$\{1,2,\ldots,N\}$$$.
  • For all $$$x$$$ and $$$y$$$ ($$$1 \leq x,y \leq N$$$), there is a sequence of bijections $$$q_1,q_2,\ldots,q_K$$$ such that $$$(q_K \circ q_{K-1} \circ \cdots \circ q_1)(x) = y$$$ and $$$q_i=p_i$$$ or $$$p_i^{-1}$$$ for all $$$i$$$.

Here, $$$\circ$$$ denotes function composition, and when $$$K=0$$$, $$$q_K \circ q_{K-1} \circ \cdots \circ q_1$$$ is defined as an identity function.

Input

Input is given from Standard Input in the following format:

$$$N$$$

Constraints:

  • $$$1 \leq N \leq 1000$$$
Output

If there is no solution, print $$$-1$$$. Otherwise, print the answer in the following format:

$$$K$$$

$$$p_{1,1}$$$ $$$p_{1,2}$$$ $$$\cdots$$$ $$$p_{1,N}$$$

$$$\vdots$$$

$$$p_{K,1}$$$ $$$p_{K,2}$$$ $$$\cdots$$$ $$$p_{K,N}$$$

Here, $$$p_{i,j}$$$ must be a value of $$$p_i(j)$$$.

If there are multiple solutions, you can print any of them.

Examples
Input
3
Output
3
1 3 2
2 3 1
3 1 2
Input
4
Output
3
4 3 1 2
1 4 2 3
2 4 1 3
Note

Consider the example $$$1$$$. For example, for $$$x=2,y=1$$$, we can set $$$q_1 = p_1, q_2 = p_2^{-1}, q_3 = p_3$$$ and get $$$q_3(q_2(q_1(2)))=1$$$.