经过数周的辛勤劳作和精神折磨，Byteasar 终于快要完成他新公寓的装修了。现在只剩下一面墙需要粉刷。Byteasar 将这面墙分成了 $n$ 个等宽的垂直条，每一条都需要涂上 $k$ 种颜色中的一种。为了方便起见，我们将颜色编号为 $1$ 到 $k$。随后他去购物，结果买得有点多。具体来说，他买了一套促销的滚筒刷，每个滚筒刷上预涂了两种颜色的漆。每个滚筒刷都有两种颜色（可能相同），分别位于左侧和右侧，允许 Byteasar 用这两种颜色粉刷两个相邻的条。这套工具非常齐全，包含了所有可能的颜色对的滚筒刷，每种颜色对各有一个。另一方面，每个滚筒刷只能使用一次，即只能用于一对相邻的条。

Byteasar 已经选好了墙面的配色方案：他希望将连续的条依次涂成颜色 $a_1, a_2, \dots, a_n$。每一条可以被多次粉刷（使用不同的滚筒），但每次粉刷时必须涂上相同的颜色。请帮助 Byteasar 判断他选择的配色方案是否可以实现。

输入格式

标准输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试数据的组数。接下来是这些测试数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n, n \ge 2$)，用空格分隔，分别表示墙上的条数和颜色数量。每组数据的第二行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$)，用空格分隔，表示墙上连续条的期望颜色。

输出格式

你的程序应向标准输出打印 $t$ 行。如果第 $i$ 组测试数据（$1 \le i \le t$）的配色方案无法实现，则在第 $i$ 行输出单词 NIE（波兰语中的“不”），否则输出单词 TAK（波兰语中的“是”）。

样例

输入格式 1

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

输出格式 1

NIE
TAK

说明

样例说明：第一组数据的答案是否定的：要粉刷这面墙，Byteasar 需要使用两次颜色为 $(2, 3)$ 的滚筒。第二组数据的配色方案可以通过使用颜色为 $(2, 2), (2, 3), (3, 2)$ 和 $(3, 1)$ 的滚筒来实现。

评分标准

测试集由以下子任务组成。每个子任务内可能包含多个测试点。