Little D recently learned about divide-and-conquer DFT on finite groups maintained by LCC on finite automata and has been showing it off everywhere.

Big D, unable to stand it anymore, gave Little D a difficult problem: for a non-deterministic finite automaton $G=(V,E_0,E_1,v_0,F)$ with an alphabet size of $2$, define $L(G)$ as the length of the shortest 01 string that is not accepted by $G$. If no such string exists, $L(G) = 0$. Big D has constrained $|V|\leq n$, and you need to construct an automaton $G$ such that $L(G)$ is as large as possible.

The rough definition of the automaton is given as follows:

• $V$ denotes the set of vertices.
• $E_0, E_1$ are two sets of directed edges defined on $V$.
• $v_0 \in V$ denotes the starting vertex.
• $F \subset V$ denotes the set of accepting vertices.
• The automaton $G$ accepts a 01 string $S$ of length $k$ if and only if there exists a sequence of vertices $v_0, v_1, \dots, v_k$ such that $v_k \in F$ and $(v_{i-1}, v_i) \in E_{S_i}$.

Input

A single integer $n$.

Output

Output the automaton $G$. It is required that $V=\{0, 1, \dots, n-1\}$ and $v_0=0$.

First, output $E_0$ in the following format:

The first line contains an integer $|E_0| \in [0, 1000]$.

The next $|E_0|$ lines each contain two integers $u, v$ representing an edge $(u, v)$.

Next, output $E_1$ in the same format.

Finally, output $F$ in the following format:

The first line contains an integer $|F|$.

The next line contains $|F|$ integers representing the elements in $F$.

Examples

Input 1

3

Output 1

2
0 0
2 2
4
0 1
1 0
0 2
2 1
3
0 1 2

Note 1

The shortest string that is not accepted is 1010.

Constraints

There are only two test cases for this problem:

The first test case is $n=6$, and your score is $50\max(0, \min(1, \frac{L(G)-11}{10}))$.

The second test case is $n=20$, and your score is $50\max(0, \min(1, \frac{\sqrt{L(G)}}{20}))$.