如果满足以下条件,我们将 n 个顶点的无向图称为 p-interesting:
- 该图恰好包含 2n + p 条边;
- 该图不包含自环和多重边;
- 对于任何整数 k (1 ≤ k ≤ n),任何由 k 个顶点组成的子图最多包含 2k + p 条边。
图的子图是图顶点的某些集合和图边的某些集合。此时,边集必须满足条件:该集中的每条边的两端必须属于所选的顶点集。
你的任务是找到一个由 n 个顶点组成的 p 有趣图。
输入
第一行包含一个整数 t (1 ≤ t ≤ 5) — 输入中的测试数量。接下来的 t 行每行包含两个空格分隔的整数: n, p (5 ≤ n ≤ 24; p ≥ 0; $$2n + p \leq \frac{n(n-1)}{2}$$) — 图中的顶点数和适当测试的兴趣值。
保证所需的图存在。
输出
对于每个 t 测试,打印 2n + p 行,其中包含 p 个有趣图的边的描述:第 i 行必须包含两个空格分隔的整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi) — 两个顶点,由结果图中的边连接。考虑用 1 到 n 的整数编号的图顶点。
按照输入中测试发生的顺序打印测试的答案。如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
1 6 0
输出 #1
1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6