사원수 Dijkstra

네덜란드의 컴퓨터 과학자 Edsger Dijkstra는 자신의 이름이 붙은 최단 경로 알고리즘을 비롯해 여러 업적을 남겼다. 이 문제는 그 알고리즘과 관계가 없다.

알고리즘 시험에서 "Dijkstra"의 철자를 틀려 1점을 잃었다. D와 stra 사이에 i, j, k 중 하나인 문자를 여러 개 적었기 때문이다. 잃은 점수를 되찾으려고 복소수를 확장한 수 체계인 사원수를 근거로 든다. 사원수의 곱셈은 다음 표를 따른다.

앞의 사원수는 행에서, 뒤의 사원수는 열에서 찾아 만나는 칸의 값을 읽는다. 예를 들어 $a \times b$에서 $a = i$, $b = j$이면 $i$ 행과 $j$ 열이 만나는 칸의 값인 $k$이고, $a = j$, $b = i$이면 $j$ 행과 $i$ 열이 만나는 칸의 값인 $-k$이다.

이 예에서 보듯 사원수의 곱셈은 교환법칙을 만족하지 않는다. 즉 $a \times b \neq b \times a$인 $a$, $b$가 있다. 반면 결합법칙은 언제나 성립해서 모든 $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$로 줄어들어야 한다. 세 부분은 모두 비어 있으면 안 된다. 예를 들어 jij는 $j \times i \times j$로 계산한다. $j \times i = -k$이고 $-k \times j = i$이므로 jij는 $i$로 줄어든다. 주어진 문자열을 이렇게 나눌 수 있는지 판정하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 공백으로 구분된 두 정수 $L$과 $X$가 주어지고, 둘째 줄에는 i, j, k 중 하나인 문자 $L$개로 이루어진 문자열이 주어진다. 이 문자열에는 음수 부호나 1을 비롯한 다른 문자가 들어 있지 않다. 판정 대상 문자열은 주어진 문자열을 $X$번 이어 붙인 것이다. 예를 들어 $L = 4$, $X = 3$이고 주어진 문자열이 kiij이면 판정 대상 문자열은 kiijkiijkiij이다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 판정 대상 문자열을 위 조건에 맞게 세 부분으로 나눌 수 있으면 YES, 나눌 수 없으면 NO이다.

첫 번째 예제의 테스트 케이스는 다음과 같다.

• 1번: 문자열이 짧아서 세 부분으로 나눌 수 없다.
• 2번: i, j, k로 나누면 된다.
• 3번: 세 부분으로 나누는 방법은 k, j, i 하나뿐인데 조건을 만족하지 않는다.
• 4번: 판정 대상 문자열은 jijijijijiji이다. $i$로 줄어드는 jij, $j$로 줄어드는 iji, $k$로 줄어드는 jijiji로 나눌 수 있다.
• 5번: 어떻게 나누어도 $j$나 $k$로 줄어드는 부분이 나오지 않는다.