有 $n$ 名玩家排成一排，共有 $m$ 种身份卡。玩家编号为 $1 \sim n$。编号是公开的，这意味着每个人都知道彼此的编号。

主持人会给每位玩家发一张身份卡。然而，接收者不允许查看自己的身份。

所有人闭上眼睛。然后，主持人依次叫出每位玩家。该玩家会被展示其他所有人的身份卡（顺序被打乱）。玩家需要猜出自己的身份，随后闭上眼睛。在此过程中，其他所有玩家保持闭眼。

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

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含两个整数 $n, m$，由空格分隔。 输入保证 $2 \le m \le n$，$m^n \le 2.1 \times 10^6$，$\sum m^n \le 1.4 \times 10^7$。

输出格式

对于每个测试用例，输出 $n$ 行，第 $p$ 行表示玩家 $p$ 的策略。 定义一个序列 $s$ 为有效序列，当且仅当 $s$ 是一个长度为 $n-1$ 且包含 $[1, m]$ 中整数的非递减序列。设有效序列的总数为 $c$，则输出 $c$ 个介于 $1$ 和 $m$ 之间的整数，其中第 $k$ 个整数表示当玩家看到的身份卡多重集等于按字典序排序后的第 $k$ 个有效序列所对应的多重集时，该玩家所作出的猜测。

样例

输入 1

1
2 2

输出 1

1 2
2 1