You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 给他的 $n$ 只猫咪进行了编号，第 $i$ 只猫咪的编号为 $a_i$，初始 $a_i=i$，即编号就是从 $1\sim n$。

猫咪们很不喜欢当前的编号，要求 Csvoner 对她们的编号进行修改，她们希望最后编号为 $n-1$ 个 $1$ 和一个 $2$（$2$ 在什么位置无所谓）。

Csvoner 想到了一个非常有趣的修改方法，他每次可以挑选两只猫咪，然后把其中一只猫咪的编号改为她除以另一只猫咪向上取整后的结果。

更具体的，他每次可以挑选两个 $1\sim n$ 之内的不同的数 $p,q$，然后把 $a_p$ 的值变为 $\lceil \frac{a_p}{a_q}\rceil$。

现在猫咪给了 Csvoner 最多 $m$ 次修改机会，请你给一个修改方案。当然猫咪非常仁慈，所以你不需要让修改次数最小，只要不超过 $m$ 即可。

输入格式

第一行一个整数 $t$，表示测试数组组数。

接下来 $t$ 行，每行两个整数，即第 $i$ 组测试数据的 $n,m$

输出格式

输出 $t$ 组结果，每组结果对应一组数据，每组结果格式如下：

第一行一个正整数 $x$，表示你的修改方案的步数。

接下来 $x$ 行，每行两个整数，即你这一步操作的 $p$ 与 $q$。

2
3 10
4 10

2
3 2
3 2
3
3 4
4 2
2 4

样例解释

• 样例 1：
  • 初始：$\{1,2,3\}$
  • $a_3=\lceil\frac{a_3}{a_2}\rceil =\lceil\frac{3}{2}\rceil = 2$：$\{1,2,2\}$
  • $a_3=\lceil\frac{a_3}{a_2}\rceil =\lceil\frac{2}{2}\rceil = 1$：$\{1,2,1\}$
• 样例 2：
  • 初始：$\{1,2,3,4\}$
  • $a_3=\lceil\frac{a_3}{a_4}\rceil =\lceil\frac{3}{4}\rceil = 1$：$\{1,2,1,4\}$
  • $a_4=\lceil\frac{a_4}{a_2}\rceil =\lceil\frac{4}{2}\rceil = 2$：$\{1,2,1,2\}$
  • $a_2=\lceil\frac{a_2}{a_4}\rceil =\lceil\frac{2}{2}\rceil = 1$：$\{1,1,1,2\}$

数据规模与约定

对于 $100\%$ 的数据，$1 \le t \le 100$，$3\le n\le 2\times 10^5$，保证 $t$ 组数据的 $n$ 之和不超过 $2\times 10^5$。

• 子任务 1（30 分）：保证 $m= 2\times n$。
• 子任务 2（30 分）：保证 $m= n+20$。
• 子任务 3（40 分）：保证 $m=n+5$。