荷兰计算机科学家 Edsger Dijkstra 对该领域做出了许多重要贡献，其中包括以他名字命名的最短路径算法。本题与该算法无关。

你在一次算法考试中因为拼写错误“Dijkstra”而被扣了一分——在 D 和 stra 之间，你写了若干个字符，每个字符要么是 i，要么是 j，要么是 k。你准备通过四元数（quaternions）来争取拿回这一分。四元数是一种从复数扩展而来的数系，具有以下乘法结构：

要将一个四元数乘以另一个四元数，请查看第一个四元数所在的行和第二个四元数所在的列。例如，要计算 $i \times j$，查看 $i$ 行和 $j$ 列，结果为 $k$。要计算 $j \times i$，查看 $j$ 行和 $i$ 列，结果为 $-k$。

如上例所示，四元数不满足交换律，即存在某些 $a$ 和 $b$ 使得 $a \times b \neq b \times a$。但它们满足结合律，即对于任何 $a$、$b$ 和 $c$，都有 $a \times (b \times c) = (a \times b) \times c$。

四元数前的负号遵循常规运算规则——对于任何四元数 $a$ 和 $b$，都有 $-a \times -b = a \times b$，以及 $-a \times b = a \times -b = -(a \times b)$。

你希望证明你的拼写错误等同于正确的拼写 ijk，方法是展示你可以将你的 i、j、k 字符串在两个位置切开，形成三个子串，使得最左边的子串在四元数乘法下归约为 $i$，中间的子串归约为 $j$，右边的子串归约为 $k$。（例如，jij 将被解释为 $j \times i \times j$；$j \times i$ 是 $-k$，$-k \times j$ 是 $i$，因此 jij 归约为 $i$。）如果这可行，你就能拿回这一分。你能找到实现的方法吗？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含一行，包含两个空格分隔的整数 $L$ 和 $X$，随后是一行包含 $L$ 个字符的字符串，所有字符均为 i、j 或 k。注意，字符串中不包含负号、1 或任何其他字符。你需要评估的字符串是给定的 $L$ 个字符的字符串重复 $X$ 次后的结果。例如，当 $L = 4$，$X = 3$，给定字符串为 kiij 时，你的输入字符串为 kiijkiijkiij。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 YES 或 NO，取决于字符串是否能按上述方式拆分为三个分别归约为 $i$、$j$ 和 $k$ 的部分。

数据范围

$1 \le T \le 100$ $1 \le L \le 10000$

小数据集

$1 \le X \le 10000$ $1 \le L \times X \le 10000$

大数据集

$1 \le X \le 10^{12}$ $1 \le L \times X \le 10^{16}$

样例

输入 1

5
2 1
ik
3 1
ijk
3 1
kji
2 6
ji
1 10000
i

输出 1

Case #1: NO
Case #2: YES
Case #3: NO
Case #4: YES
Case #5: NO

说明

在 Case #1 中，字符串太短，无法拆分为三个子串。

在 Case #2 中，只需将字符串拆分为 i、j 和 k。

在 Case #3 中，将字符串拆分为三部分的唯一方法是 k、j、i，这不满足条件。

在 Case #4 中，字符串为 jijijijijiji。它可以拆分为 jij（归约为 $i$）、iji（归约为 $j$）和 jijiji（归约为 $k$）。

在 Case #5 中，无论你如何选择子串，它们都无法归约为 $j$ 或 $k$。