题目描述

Jernej 在晚上感到很无聊，于是他发明了一个游戏。他想要用数字卡片生成一个塔。一开始，他在一张卡片上写下了一个数字 $1$。

Jernej 可以再另一张写下一个新的数字并放在塔顶。 这个新的数字必须等于之前塔中某一连续段的数字之和 。也就是说，假设现在塔中已有 $n$ 个数字，你可以任意选取塔中的一段 $[l,u]$ ，并对这一段求和，将得到的新数字添加至塔顶，其中 $1\le l\le u\le n$。

Jernej 想要生成 $T$ 个塔（相当于多组询问），每个塔顶都是 $T$ 个可能不同的他想要的数字。你需要帮助他求出生成这些塔的最小步数及其方案。

输入格式

第一行：一个整数 $T$，表示塔的个数；

接下来 $T$ 行，一行一个整数 $q$，表示现在 Jernej 想生成一个塔顶数字为 $q$ 的塔。

保证有解。

输出格式

对于每个询问 $q$：

• 输出一行，包含一个整数 $s$ （$0\le s\le 10^3$），表示最小步数。
• 接下来 $s$ 行，每行两个由空格隔开的整数 $l,u$，表示建生成塔的方案（操作时间早的先输出）。

3
2
3
7

2
1 1
1 2
3
1 1
2 2
1 3
4
1 1
1 2
2 3
1 4​

提示

【Special Judge 计分标准】

本题共 $10$ 个测试点。对于每个测试点，计分规则如下：

• 对于测试点中的任意一个塔，如果你的程序输出的 最小步数 与标准答案 均一致 ，那么这个测试点你会得到 $10$ 分。
• 对于测试点中的任意一个塔，如果你的程序输出的答案是错误的，那么得 $0$ 分（评测时如果发现输出不完全可能会得到 UKE）。
• 如果你的答案并 不是最优解但不是错误的 ，那么对于该测试点中的第 $i$ 个塔，你得到的分数为 $\text{score}_i =1+\dfrac{\text{minimum steps}}{\text{solution steps}}\times 7$，其中 $\text{minimum steps}$ 表示正确答案的最小步数，$\text{solution steps}$ 表示你的程序输出的答案。最终这个测试点的得分为 $\min\limits_{i\in [1,T]} \{\text{score}_i\}$。向上取两位小数。

【输入输出样例解释】

询问 1 解释：

• Jernej 想要生成造一个塔顶数为 $2$ 的塔。起初塔为 $\{1\}$（左边表示塔底，右边表示塔顶）；
• 第一步，选取子段 $[1,1]$，对 $\{1\}$ 中的所有元素求和，得到 $1$，现在塔为 $\{1,1\}$；
• 第二步，选取子段 $[1,2]$，对 $\{1,1\}$ 中的所有元素求和，得到 $2$，现在塔为 $\{1,1,2\}$。此时已经达到了询问的要求。

询问 2 解释：

• 要生成塔顶为 $3$ 的塔不止一种方法。除了样例输出的一种之外，下面的也是正确答案：

1 1
1 2
2 3

【数据规模与约定】

本题采用多测试点捆绑测试，共有 7 个子任务。

• Subtask 1（1 test case - 10 points）：$T\le 10,q\le 10$。
• Subtask 2（1 test case - 10 points）：$T\le 20,q\le 20$。
• Subtask 3（1 test case - 10 points）：$T= 100,q\le 100$。
• Subtask 4（1 test case - 10 points）：$T= 10^3,q\le 10^4$。
• Subtask 5（1 test case - 10 points）：$T= 10^3,q\le 10^5$。
• Subtask 6（1 test case - 10 points）：$T= 10^3,q\le 10^6$。
• Subtask 7（1 test case - 10 points）：$T= 10^3,q\le 10^9$。
• Subtask 8（1 test case - 10 points）：$T= 10^3,q\le 10^{12}$。
• Subtask 9（2 test case - 20 points）：无其他限制。

对于所有数据，保证 $1\le T\le 10^3,1\le q\le 10^{18}$

【说明】

原题来自：eJOI2019 Problem D. Tower。

翻译提供：@_Wallace_