Fake Plastic Trees

트리는 재귀적인 구조이며, 다음 중 하나이다.

• 빈 트리. 빈 트리는 $-1$로 표기하고 크기는 0이다.
• 비어 있지 않은 트리. 비어 있지 않은 트리 $T$는 두 트리의 쌍 $(T_1,\ T_2)$로 표기한다. $T_1$을 $T$의 왼쪽 서브트리, $T_2$를 $T$의 오른쪽 서브트리라고 한다. $T = (-1,\ -1)$이면 $T$를 리프라고 한다. 리프의 크기는 1이고, 리프가 아닌 트리의 크기는 $|T_1| + |T_2|$이다. 여기서 $|T_1|$은 $T_1$의 크기, $|T_2|$는 $T_2$의 크기이다.

비어 있지 않은 트리 $T$가 균형을 이루면 $T$를 Fake Plastic Tree라고 한다. 구체적으로 $T = (T_1,\ T_2)$일 때 $|T_1| = |T_2|$ 또는 $|T_1| = |T_2| + 1$이면 $T$는 Fake Plastic Tree이다.

컴퓨터 과학에서 트리는 자료 구조로 흔히 쓰이며 메모리에 저장된다. 처음에는 메모리에 트리가 없고, 가상의 널 포인터만 있다. 널 포인터는 빈 트리 $-1$에 대응한다. $T_1$과 $T_2$를 널 포인터나 기존 트리의 포인터로 정하면 트리를 메모리에 할당할 수 있다. 그러면 메모리에 $T = (T_1,\ T_2)$가 추가되면서 구조가 확장된다. 포인터는 작은 정수로 표현할 수 있으므로 트리 전체를 명시적으로 저장할 필요가 없다.

형식적으로 메모리 $M$은 귀납적으로 정의되는 구조이며, 처음에는 빈 트리 $-1$만 포함한다. ($M = \{-1\}$.) 다음 연산으로 메모리를 확장할 수 있다. $M \leftarrow M \cup \{(T_1,\ T_2)\}$, 여기서 $T_1 \in M,\ T_2 \in M$이다. 트리 $T$가 $i$번째 단계에서 삽입되면 $T$는 인덱스 $i-1$을 가진다. 인덱스 $i$인 트리의 서브트리는 $[-1,\ i-1]$ 범위의 정수 쌍으로 나타낼 수 있다.

여러분의 과제는 다음 조건을 만족하는 메모리 $M$을 구성하는 것이다.

• $M$의 모든 트리는 빈 트리이거나 Fake Plastic Tree이다.
• $M$은 비어 있지 않은 트리를 125개 이하로 가진다.
• $|T| = N$인 트리 $T \in M$이 존재한다. $N$은 정수이며 입력으로 주어진다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. ($1 \leq T \leq 2,000$)

다음 $T$개 줄에 정수 $N$이 하나씩 주어진다. $N$은 여러분의 트리가 가져야 하는 리프의 수이다. ($1 \leq N \leq 10^{18}$)

각 테스트 케이스마다 $V + 2$개 줄을 출력한다. $V$는 $M$에 있는 비어 있지 않은 트리의 수이다. ($1 \leq V \leq 125$)

첫째 줄에 정수 $V$를 출력한다.

다음 $V$개 줄에 두 정수 $L_i,\ R_i$를 공백으로 구분해 출력한다. 이는 인덱스 $i$인 트리의 왼쪽 서브트리와 오른쪽 서브트리의 인덱스이다. ($-1 \leq L_i,\ R_i \leq i - 1$)

$(V+2)$번째 줄에 $N$개의 노드를 가진 트리의 인덱스 $P$를 출력한다. ($0 \leq P \leq V-1$)

주어진 조건에서 답이 항상 존재함이 보장된다.