Dijkstra (Large)

A shortest path algorithm carries the name of the Dutch computer scientist Edsger Dijkstra. 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 them i, j, or k. To get the point back you appeal to the quaternions, a number system extended from the complex numbers whose multiplication follows this table.

To multiply one quaternion by another, read the cell where the row of the first factor meets the column of the second factor. For example, $i \times j$ is $k$, and $j \times i$ is $-k$.

Quaternion multiplication is not commutative: there are $a$ and $b$ with $a \times b \ne b \times a$. It is associative: for all $a$, $b$, $c$ we have $a \times (b \times c) = (a \times b) \times c$.

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

You want to show that what you wrote is equivalent to the correct spelling ijk. Cut the string at two positions into three non-empty pieces so that, under quaternion multiplication, the first piece reduces to $i$, the middle piece reduces to $j$, and the last piece reduces to $k$. For example, jij is read as $j \times i \times j$: $j \times i$ is $-k$, and $-k \times j$ is $i$, so jij reduces to $i$. Decide whether such a cut exists.

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

Limits

• $1 \le T \le 100$
• $1 \le L \le 10000$
• $1 \le X \le 10^{12}$
• $1 \le L \times X \le 10^{16}$

For each test case print one line Case #x: y, where $x$ is the test case number starting from 1, and $y$ is YES if the string can be cut into three pieces reducing to $i$, $j$, and $k$ in that order, and NO otherwise.

The five cases of the first sample input work out as follows.

In case 1 the string is too short to be split into three pieces.

In case 2, split the string into i, j, and k.

In case 3 the only split into three pieces is k, j, i, and that split does not meet the condition.

In case 4 the string is jijijijijiji. It splits into jij, which reduces to $i$, then iji, which reduces to $j$, then jijiji, which reduces to $k$.

In case 5 no cut ever produces a piece that reduces to $j$ or to $k$.