“至尊戒，驭众戒，至尊戒，寻众戒，至尊戒，唤众戒，禁锢众戒于黑暗中……” 真的吗？黑暗巫师 Byteon 永远无法理解这一点。索伦怎么会如此鲁莽，让自己的命运仅仅系于一枚戒指，还在铭文中大肆吹嘘？

Byteon 也从魔法戒指中汲取力量，但为了避免索伦的命运，他并没有把一切都押在一件小首饰上。在他的黑塔前有一排 $n$ 根魔法柱，每根柱子上恰好有 $k$ 个彩色戒指。

善良的巫师 Bitalf 预言，力量源于多样性，当每根柱子上的戒指颜色单一（或为空）时，Byteon 就会失去力量。Bitalf 本人不愿意移动这些戒指，但他变出了两根额外的柱子——一根在结构的最左侧，另一根在最右侧（所以现在总共有 $n+2$ 根柱子，最外侧的两根是空的，而其他所有柱子上仍然恰好有 $k$ 个戒指）。

移动戒指的工作（一如既往地）落在了霍比特人 Bitbo Byteins 的身上。每天，Bitbo 都会悄悄爬上一根柱子，将该柱子最顶端的戒指移动到相邻柱子的顶部。幸运的是，Byteon 的邪恶之眼多年来已经失去了警惕，不会注意到这个小小的霍比特人，也不会注意到戒指的区别。然而，任务的复杂之处在于，没有任何一根柱子能容纳超过 $k$ 个戒指。

没人确定 Bitalf 的预言是否有意义，以及戒指是否能相应地移动。请帮助这位勇敢的霍比特人制定一个计划！计划的长度不应超过一百万天，这样 Bitbo 才有机会活到故事的结局。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 25$)。接下来是各个测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($1 \le n \le 50, 1 \le k \le 10$)。

接下来的 $n$ 行中，每行包含一个数字序列：$a_{i1}, a_{i2}, \dots, a_{ik}$ ($0 \le a_{ij} \le 10^9$)，表示第 $i$ 根柱子上从底到顶的戒指。编号为 $0$ 和 $n+1$ 的柱子存在，但初始为空。

所有测试用例的 $n$ 之和不超过 $50$。

输出格式

对于每个测试用例，如果可以通过放置戒指使得每根柱子上的戒指颜色最多只有一种，则输出 TAK，否则输出 NIE。

如果答案是肯定的，请在接下来的行中输出一个实现目标的计划。第一行输出移动次数 $p$ ($0 \le p \le 10^6$)。在接下来的 $p$ 行中，每行输出两个整数 $a_i, b_i$ ($0 \le a_i, b_i \le n+1, |a_i - b_i| = 1$)，表示 Bitbo 应将第 $a_i$ 根柱子顶部的戒指移动到第 $b_i$ 根柱子的顶部。在执行此操作之前，第 $a_i$ 根柱子不能为空，而第 $b_i$ 根柱子必须包含少于 $k$ 个戒指。

如果有多种可能的计划，你可以打印其中任何一个，只要不超过 $10^6$ 次移动的限制即可。

样例

输入 1

2
2 2
1 2
2 1
1 4
1 2 3 4

输出 1

TAK
2
1 0
2 1
NIE