Quaternion Dijkstra

The Dutch computer scientist Edsger Dijkstra left many results behind, among them the shortest path algorithm that carries his name. This problem is not about that algorithm.

You lost one point on an algorithms exam for misspelling "Dijkstra". Between D and stra you wrote some number of characters, each of which was i, j, or k. To win the point back you appeal to quaternions, a number system extended from the complex numbers. Quaternion multiplication follows this table.

Look up the first quaternion in the rows and the second one in the columns, then read the cell where they meet. For example, in $a \times b$ with $a = i$ and $b = j$ the cell holds $k$, and with $a = j$ and $b = i$ the cell holds $-k$.

As those examples show, quaternion multiplication is not commutative: there are $a$ and $b$ with $a \times b \neq b \times a$. It is associative, so $a \times (b \times c) = (a \times b) \times c$ holds for all $a$, $b$, and $c$.

Signs behave the usual way. For all quaternions $a$ and $b$, $(-a) \times (-b) = a \times b$, and $(-a) \times b = a \times (-b) = -(a \times b)$.

To argue that your misspelling equals the correct spelling ijk, cut the string in two places into three substrings so that the leftmost one reduces to $i$, the middle one reduces to $j$, and the rightmost one reduces to $k$. None of the three substrings may be empty. For example, jij is evaluated as $j \times i \times j$. Here $j \times i = -k$ and $-k \times j = i$, so jij reduces to $i$. Decide whether the given string admits such a split.

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case has two lines. The first line contains two space separated integers $L$ and $X$, and the second line contains a string of $L$ characters, each of which is i, j, or k. The string never contains a minus sign, a 1, or any other character. The string you must evaluate is the given string repeated $X$ times. For example, with $L = 4$, $X = 3$, and the given string kiij, the string to evaluate is kiijkiijkiij.

Limits

• $1 \le T \le 100$
• $1 \le L \le 10000$
• $1 \le X \le 10000$
• $1 \le L \times X \le 10000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is YES if the evaluated string can be split into three parts under the rule above, and NO otherwise.

The test cases of the first example work out as follows.

• Case 1: the string is too short to be split into three parts.
• Case 2: split it into i, j, and k.
• Case 3: the only split into three parts is k, j, i, and it does not meet the condition.
• Case 4: the evaluated string is jijijijijiji. It splits into jij, which reduces to $i$, then iji, which reduces to $j$, then jijiji, which reduces to $k$.
• Case 5: no split ever produces a part that reduces to $j$ or to $k$.