16184번 - Fake Plastic Trees 스페셜 저지다국어

Tree is a recursive structure, which is either:

• Empty. Empty tree is denoted as $-1$ and has a size of 0.
• Non-empty. Non-empty tree $T$ is denoted as a pair of two trees $(T_1,\ T_2)$, where $T_1$ is called left subtree of $T$, and $T_2$ is called right subtree of $T$. If $T = (-1,\ -1)$, then we call such $T$ a leaf. Leaf has a size of 1, and non-leaf has a size of $|T_1| + |T_2|$, where $|T_1|$ is the size of $T_1$, and $|T_2|$ is the size of $T_2$.

A non-empty tree $T$ is a Fake Plastic Tree, if the tree is balanced. Formally, Let $T = (T_1,\ T_2)$. If $|T_1| = |T_2|$ or $|T_1| = |T_2| + 1$ holds, then $T$ is a Fake Plastic Tree.

In computer science, trees are commonly used as a data structure, and they are stored in a memory. At first, there are no trees in the memory, and only an imaginary null pointer exists (which corresponds to empty tree, $-1$). You can allocate a tree in the memory, by setting $T_1$ and $T_2$ as either a null pointer or a pointer of an existing tree. Then, the memory is extended by adding $T = (T_1,\ T_2)$ into its structure. Note that pointer can be described as a small integer, reducing the need for explicitly storing the whole tree.

Formally, memory $M$ is an inductive structure, which at first contains only empty tree $-1$. ($M = \{-1\}$). You can expand the memory with following operation $M \leftarrow M \cup \{(T_1,\ T_2)\}$, where $T_1 \in M,\ T_2 \in M$. If a tree $T$ is inserted in $i$-th stage, then it has the index $i-1$. For a tree with index $i$, their subtrees can be represented as a pair of integer in range $[-1,\ i-1]$.

Your task is to construct a memory $M$, which satisfies the following:

• Every tree in $M$ is either empty or Fake Plastic Tree.
• $M$ has at most 125 non-empty trees.
• There exists a tree $T \in M$, where $|T| = N$ holds. $N$ is an integer, and is given as an input.

The first line contains a single integer $T$, the number of test cases. ($1 \leq T \leq 2,000$)

In the next $T$ lines, a single integer $N$ is given, which indicates the number of leaves your tree should contain. ($1 \leq N \leq 10^{18}$)

For each case, you should print $V + 2$ lines, where $V$ is the number of non-empty trees in $M$. ($1 \leq V \leq 125$).

In the first line, you should print single integer $V$.

In the next $V$ lines, you should print two space-separated integer $L_i,\ R_i$, which indicates the index of left subtree and right subtree for a tree with index $i$. ($-1 \leq L_i,\ R_i \leq i - 1$).

In the $(V+2)$-th line, you should print $P$, the index of the tree which contains $N$ nodes. ($0 \leq P \leq V-1$).

It is guaranteed that an answer always exists under the given condition.