狼人

中文题目为机翻，原题目请参考英文题面

有 $n$ 玩家坐成一排，有 $m$ 种身份卡。玩家的编号从 $1 \sim n$ 开始。 编号是公开的，也就是说每个人都知道对方的编号。

主持人会给每个玩家一张身份卡。但是，接收者不允许查看他们的身份。

所有人都闭上眼睛。然后，主持人会依次叫出每位玩家。所有其他玩家的身份卡都会被打乱，展示给该玩家。该玩家应猜出自己的身份，然后闭上眼睛。在此过程中，所有其他玩家都将保持闭眼状态。

游戏开始前，玩家有足够的时间讨论，并希望确保至少有 $\lfloor \frac{n}{m} \rfloor$ 的猜测是正确的。请帮他们制定一个策略。

输入

第一行包含一个整数 $T$，表示测试案例的数量。

每个测试用例包含两个整数 $n,m$，中间用空格隔开。

输入保证 $2 \leq m \leq n,m^n \leq 2.1 \times 10^6, \sum m^n \leq 1.4 \times 10^7$.

输出

对于每个测试案例，输出 $n$ 行，行 $p$ 表示玩家 $p$ 的策略。

当且仅当 $s$ 是长度为 $n − 1$ 且包含 $[1，m]$ 中的整数时，表示序列 $s$ 有效。表示有效序列 $c$ 的计数，然后输出 $1$ 和 $m$ 之间的整数 $c$，第 $k$ 个整数表示当看到的身份证多集等于按词典顺序排序的第 $k$ 个有效序列的多集时，玩家将猜到的内容。

示例

1
2 2

1 2
2 1

注意，本题为 Special judge