题目背景

2025.5.6：加强操作次数限制，并调整了部分分设计。

2025.5.8：再次加强操作次数限制，并调整了部分分设计。之前的提交记录已经全部重测。

题目描述

有一列实数，对于每一次操作，可以选择两个实数，把它们同时变为两数之积。

例如，给定 $7, 4, 5$，对 $7$ 和 $5$ 进行一次操作，原数列变为 $35, 4, 35$。

给定数列的长度 $n$，你的目标是找到一种操作方案，使得对于任意长度为 $n$ 的实数列，按照该操作方式操作之后，数列的每一项数值都相同。

输入格式

本题有多组测试数据。

第一行输入数据组数 $T$。

对于每组数据有一行，包含一个正整数 $n$，表示数列长度。

输出格式

对于每组数据，先输出一个整数表示能否找到。若能输出 $1$，否则输出 $0$。

若能找到，还需要输出一行 $m$ 表示操作次数（你需要保证 $0 \leq m \leq 5 \times 10^5$），接下来 $m$ 行，每行包含两个整数，表示操作的两项在数列中的编号。

3
2
3
4

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

提示

Idea：Milmon，Solution：Milmon & _fewq，Code：Milmon & _fewq，Data：Milmon，Check：Konata28。

对于所有测试数据，保证 $T = 20$，$2 \leq n \leq 2^{10}$。本题共包含 $3$ 个子任务：

对于子任务 1，选手只需要正确回答是否存在操作方案即可获得满分。

对于子任务 2，对于每组测试数据分别计分：对于一组测试数据，只要选手正确回答是否存在操作方案，并且给出的操作方案均合法，就可以得到该测试点 $5 \%$ 的分数。选手在该测试点得到的分数等于每组测试数据得分的总和。

对于子任务 3：

• 若存在一组测试数据，选手没有正确回答是否存在操作方案，或者给出的操作方案不合法，那么选手在该测试点不得分；

• 否则，若对于所有存在操作方案的测试数据，选手都给出了操作次数不超过 $2n - 1$ 的方案，那么选手在该测试点得到全部分数；

• 否则，设所有存在操作方案的测试数据中选手给出的最大操作次数为 $s$，定义函数：

  $$f(x) = \frac{2 \times 10^7}{(x + 4\,000)^{0.7}}$$

  则选手在该测试点的得分为：

  $$\frac{f(s) - f(500\,000)}{f(2\,047) - f(500\,000)} \times 55 $$

  下表为在一些特殊的 $s$ 中选手在该测试点得到的分数：

  $s =$	选手得分
  $500\,000$	$0$
  $400\,000$	$0.436$
  $300\,000$	$1.106$
  $200\,000$	$2.302$
  $100\,000$	$5.258$
  $50\,000$	$9.836$
  $10\,000$	$29.402$
  $5\,000$	$41.003$
  $3\,000$	$49.391$
  $2\,047$	$55$

提示：若能够完成正确性判断，但是无法完成构造的，也需要按照输出格式输出，例如你可以输出一个 $m = 0$ 的构造。类似地，输出时请判定 $0 \leq m \leq 5 \times 10^5$ 是否成立，若评分时存在一组数据的 $m > 5 \times 10^5$，则你无法得到任何分数。