Bytie 和他的朋友们打算穿过 Byteburg 的主干道。人行横道由路面上交替的白色和黑色条纹组成。Bytie 吹嘘说他可以穿过街道而不踩到任何白色条纹。

Bytie 的鞋长为 $s$，步长为 $k$。他可以从人行横道一侧的任意一点开始行走。之后，他必须以相等的步长沿横道（即垂直于街道方向）行走，且不能踩到（或部分踩到）任何白色条纹。不过，Bytie 鞋子的前端或后端可以与白色条纹“相切”。在最后一步之后，Bytie 必须双脚都站在街道另一侧的人行道上。他可以在同一条黑色条纹上踩多次，也可以完全不踩某条黑色条纹。

不幸的是，Bytie 的任务比他预想的要复杂，因为奇怪的是，横道上的条纹并不是均匀涂抹的……请帮助 Bytie 检查他是否能像他宣称的那样穿过街道。

输入格式

标准输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。接下来有 $2t$ 行，包含各测试用例的描述。每个描述的第一行包含三个整数 $s$、$k$ 和 $n$ ($1 \le s < k \le 10^{9}$，$2 \le n \le 500\,000$)，分别代表 Bytie 的鞋长、步长以及人行横道上的条纹数量。第二行包含 $n$ 个整数 $p_{i}$ ($1 \le p_{i} \le 10^{9}$)，代表横道上各条纹的长度：第一条是白色，第二条是黑色，第三条是白色，以此类推。

输出格式

程序应向标准输出输出 $i$ 行。第 $i$ 行应包含一个单词 TAK 或 NIE（波兰语中的“是”或“否”），取决于 Bytie 是否能按照上述规则穿过第 $i$ 个测试用例中的街道。

样例

输入 1

2
2 8 7
2 5 6 3 2 1 2
2 8 4
1 6 7 4

输出 1

TAK
NIE

该图展示了 Bytie 在第一个测试用例中应如何穿过街道。