每一个玩过“井字棋”的人迟早都会意识到，存在一种简单的策略可以保证平局，这使得这个游戏变得有些乏味。在本题中，我们不再考虑经典“井字棋”游戏中的最优走法，而是考虑其更通用的变体，并解决一个逆向问题：对于给定的棋盘状态，它是否可能是某个正确游戏结束时的状态？

为了本题的目的，我们假设游戏在一个 $n \times n$ 的棋盘上进行，棋盘由（初始为空的）单位方格组成。玩家轮流落子，每次移动时将自己的符号（其中一名玩家为圆圈，另一名玩家为叉号）放置在选定的空位上。第一步可以由任何一名玩家开始。在玩家完成落子后，如果出现了 $k$ 个连续的相同符号（水平、垂直、对角线或反对角线方向），则对应的玩家获胜，游戏结束。最后，如果双方均未获胜且棋盘已填满，则判定为平局。

输入包含一个带有若干圆圈、叉号和空位的棋盘。请判断是否存在一个合法的游戏过程，使得游戏以给定的棋盘状态结束。注意，在这个假设的游戏中，玩家不必采取最优策略，他们只需要遵循上述游戏规则即可。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($3 \le n \le 6, 2 \le k \le n$)，分别表示棋盘大小和获胜所需的连续符号数。

接下来的 $n$ 行，每行包含 $n$ 个字符，描述棋盘。棋盘描述中可能的符号为 .（空格）、x（叉号）和 o（圆圈）。

输出格式

对于每个测试用例，如果给定的棋盘可以是井字棋中一个正确的最终状态，则第一行输出 TAK，否则输出 NIE。

如果答案为肯定，请在接下来的行中输出一个示例游戏过程，给出填充棋盘的可能顺序。在游戏描述的第 $i$ 行，输出两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le n$)，表示第 $i$ 步落子在第 $x_i$ 行（从上往下数）和第 $y_i$ 列（从左往右数）。

如果有多个正确答案，你可以输出其中任意一个。

样例

输入 1

7
3 3
x.o
xxx
o.o
4 3
xx.x
...o
..o.
.o..
3 3
xoo
oxx
xoo
3 2
xoo
oxx
xoo
3 3
xox
.o.
xox
3 2
xo.
..x
xo.
3 3
x..
.x.
..x

输出 1

TAK
2 2
1 3
1 1
3 3
2 1
3 1
2 3
TAK
1 1
3 3
1 2
4 2
1 4
2 4
TAK
1 2
1 1
1 3
3 1
2 1
2 2
3 2
2 3
3 3
NIE
NIE
NIE
NIE

说明

测试 1：游戏由叉号获胜。 测试 2：圆圈获胜，在反对角线方向上占据了三个连续的方格。 测试 3：游戏以平局结束。 测试 4：任何导致该棋盘状态的走法序列都会在第九步之前导致其中一名玩家获胜。 测试 5：叉号必须进行最后一步，这与圆圈获胜的事实相矛盾。 测试 6：棋盘处于合法状态，但游戏尚未结束。 测试 7：叉号走了三步，而圆圈一步未走。