很久以前，幼儿园老师带孩子们去公园玩“传声筒”游戏。有 $N$ 个孩子，每个人都知道同一个包含 $M$ 个单词的集合，我们将这些单词编号为 $1$ 到 $M$。游戏过程如下：老师将孩子们排成一列，向第一个孩子耳语单词 $1$。接着，第一个孩子将他听到的单词耳语给第二个孩子，第二个孩子再将他听到的单词耳语给第三个孩子，以此类推，直到最后一个孩子。最后，最后一个孩子大声说出他听到的单词。

由于那天年轻的计算机科学家们在附近的协会里吵闹地进行编码，孩子们无法集中注意力玩游戏，因此他们经常听到与耳语内容完全不同的单词。但已知以下事实：某个孩子对于特定的单词总是以相同的方式“听错”，即如果孩子 $D$ 被耳语了单词 $A$，那么无论他处于队列的什么位置，或者是由谁向他耳语了单词 $A$，他都会传出（如果是队列中的最后一个孩子，则大声说出）同一个单词。

为了娱乐，老师决定进行一个实验：她将这个游戏重复了 $N!$ 次，即每一种可能的孩子排列顺序都进行一次。她注意到，有一个单词恰好出现了 $K$ 次，作为最后一个孩子大声说出的单词。她想知道这是如何可能的，并请求你重建这样一种情况。

给定数字 $N$ 和 $K$。请确定词汇表的大小 $M$ 以及该词汇表中的一个单词 $X$ ($1 \le X \le M$)，并为 $N$ 个孩子中的每一个以及 $M$ 个单词中的每一个确定该孩子听到给定单词后会传出的单词，使得在 $N!$ 种排列中，最后一个孩子大声说出单词 $X$ 的次数恰好为 $K$。你的方案得分取决于所选词汇表的大小，词汇表越小得分越高。详情请参阅“评分”部分。

输入格式

第一行包含一个整数 $P$ ($1 \le P \le 2$)，表示评分部分中的子任务编号。第二行包含测试场景的数量 $T$ ($1 \le T \le 10$)。各个场景相互独立，即一个输入文件中包含多个测试用例。

接下来的 $T$ 行中，每行包含两个整数 $N$ 和 $K$ ($1 \le N \le 12, 0 \le K \le N!$)，对应一个测试场景。

输出格式

对于每个场景，第一行输出两个整数：$M$ 和 $X$ ($1 \le X \le M \le 10\,000$)，分别表示词汇表的大小和在 $K$ 场游戏中最后一个孩子大声说出的单词。在接下来的 $N$ 行中，每行输出 $M$ 个整数：第 $i$ 行的第 $j$ 个数字表示第 $i$ 个孩子在听到单词 $j$ 时会传出的单词。

子任务

测试用例分为两个子任务，请仔细阅读每个子任务的描述。如果你的程序在任何一个用例上不正确，该子任务将得 0 分。

子任务 1 总分 30 分，满足 $1 \le N \le 7$。对于此子任务，你可以获得 0 分或满分。在程序对所有用例正确的前提下，唯一的额外条件是 $M \le 10\,000$。

子任务 2 总分 70 分，满足 $1 \le N \le 12$。对于此子任务，可以获得部分分。对于每个场景，都会计算你的算法所获得的得分。你的算法将获得 $70 \cdot B$ 分，其中 $B$ 是所有场景中得分的最小值。单个场景的得分 $B_s$ 计算如下：

• 如果 $M \le N + 1$，则 $B_s = 1$
• 否则，如果 $M \le N + 5$，则 $B_s = 0.7 + 0.15 / (M - N - 1)$ (满足 $0.7 \le B_s \le 0.85$)
• 否则，如果 $M \le 5N$，则 $B_s = 0.5 + 0.05 \cdot (5 - M/N)$ (满足 $0.5 \le B_s \le 0.7$)
• 否则，如果 $M \le 10\,000$，则 $B_s = 0.5 / (\log_{10}(M / 5N) + 1)$ (满足 $0.0 \le B_s \le 0.5$)

样例

输入格式 1

1
2
3 2
2 1

输出格式 1

3 3
2 1 3
3 2 2
1 3 2
2 1
1 1
2 2

说明

在第一场游戏中，如果孩子排列顺序为 $(1, 2, 3)$，将发生以下情况：老师向第一个孩子耳语单词 $1$。他向第二个孩子耳语单词 $2$。第二个孩子向第三个孩子耳语单词 $2$，然后他大声说出单词 $3$。另一个对应的孩子排列顺序是 $(3, 2, 1)$，对于该顺序，说出的单词依次为 $1$（老师）、$1$（孩子 $3$）、$3$（孩子 $2$）、$3$（孩子 $1$）。对于其余四个排列，最后一个孩子说出的单词均不为 $3$。

输入格式 2

2
2
3 3
4 0

输出格式 2

6 2
1 2 3 4 5 6
6 5 4 3 2 1
2 4 1 4 3 2
2 2
1 1
1 1
1 1
1 1

说明

这是第二个子任务中的一个示例，该子任务具有部分评分。对于第一个场景，满足 $N + 1 < M \le N + 5$，因此该结果得分为 $0.77$（保留两位小数）。对于第二个场景，满足 $M \le N + 1$，因此该结果得分为 $1$。由于取所有测试场景中的最小值，该方案将获得此示例总分的 $0.77$ 倍。