OUPC2025 OPENコンテスト 2026/03/29 09:00 ~ 2026/03/29 14:00 5:00:00.000

D Distinct Path Set

問題
制限時間: 2 sec メモリ制限: 1024 MB
Distinct Path Set
Statement

正整数 \(N\) が与えられます。

\(3\) つの木 \(T_1, T_2, T_3\) があり、これらはそれぞれ \(1\) から \(N\) までの番号が付けられた頂点と、\(1\) から \(N-1\) までの番号が付けられた辺からなります。\(T_1, T_2, T_3\) の辺は以下を満たします。

  • \(T_1\) の辺 \(i\) は、頂点 \(i\) と頂点 \(i+1\) を結ぶ
  • \(T_2\) の辺 \(i\) は、頂点 \(1\) と頂点 \(i+1\) を結ぶ
  • \(T_3\) の辺 \(i\) は、頂点 \(\lfloor\frac{i+1}{2}\rfloor\) と頂点 \(i+1\) を結ぶ

\(k=1,2,3\) のそれぞれについて以下の問いに答えてください。

  • 以下の条件を満たす非負整数 \(m\) と、\(N\) 以下の正整数からなる数列 \(X = (X_1, X_2, \dots, X_m),Y=(Y_1, Y_2, \dots, Y_m)\) を考えます。 \(m\) としてあり得る最小値と、それを達成する \(X,Y\) を \(1\) つ求めてください。
    • 木 \(T_k\) における頂点 \(X_j, Y_j\) 間の単純パスが辺 \(i\) を含むような \(j\) の集合を \(S_i\) としたとき、\(S_1, S_2, \dots, S_{N-1}\) は相異なる。

\(1\) つの入力につき、\(Q\) 個のテストケースを解いてください。

Input

以下の形式で標準入力から与えられます。

\(Q\)
\(\mathrm{case}_{1}\)
\(\mathrm{case}_{2}\)
\(\vdots\)
\(\mathrm{case}_{Q}\)

\(q\) 番目のテストケース \(\mathrm{case}_{q}\) は以下の形式で与えられます。

\(N\)

入力は以下の制約をすべて満たします。

  • \(1 \leq Q\)
  • \(4 \leq N \leq 2 \times 10^5\)
  • \(1\) つの入力に含まれる \(N\) の総和は \(2 \times 10^5\) 以下

Output

\(Q\) 個のテストケースについて、答えを順に出力してください。

各テストケースについて、\(k=1,2,3\) の順に以下の形式で出力してください。

\(m\)
\(X_1~Y_1\)
\(X_2~Y_2\)
\(\vdots\)
\(X_m~Y_m\)

答えが複数存在する場合、どれを出力しても正解となります。

部分点を得るためには、不正解である場合についても以下の条件をすべて満たしている必要があります。

  • \(m\) は \(0\) 以上 \(N\) 以下の整数
  • \(X_i, Y_i\) は \(1\) 以上 \(N\) 以下の正整数

Scoring

各テストケースについて、正解した \(k\) の種類数を \(p'\) とします。この問題のすべてのテストケースにおける \(p'\) の最小値を \(p\) としたとき、

  • \(p=0\) なら \(0\) 点
  • \(p=1\) なら \(15\) 点
  • \(p=2\) なら \(45\) 点
  • \(p=3\) なら \(100\) 点
が与えられます。

Example

Input 1
1
4
Output 1
2
1 3
2 3
2
1 3
2 3
2
1 3
1 4

Note

入出力例 \(1\) の \(k=1\) について、\(T_1\) を下記に示します。

1 2 3 4

出力例は \(X = (1,2), Y=(3,3)\) です。

  • 頂点 \(1,3\) 間の単純パスは辺 \(1,2\) を含みます。(赤)
  • 頂点 \(2,3\) 間の単純パスは辺 \(2\) を含みます。(青)
1 2 3 4

そのため、\(S_1 = \{1\}, S_2 = \{1,2\}, S_3 = \{\}\) となり、これらは相異なります。

サンプル