다익스트라

네덜란드의 컴퓨터 과학자 Edsger Dijkstra는 자신의 이름을 딴 최단 경로 탐색 알고리즘을 비롯하여 이 분야에 많은 중요한 공헌을 했다. 이 문제는 그 알고리즘에 관한 것이 아니다.

알고리즘 시험에서 "Dijkstra"의 철자를 틀려 한 점 감점되었다. D와 stra 사이에 여러 문자를 썼으며, 각 문자는 i, j, k 중 하나였다. 점수를 되찾기 위해, 복소수에서 확장된 실제 수 체계인 사원수를 이용하여 이의를 제기하려 한다. 사원수의 곱셈 구조는 다음과 같다.

한 사원수에 다른 사원수를 곱하려면 첫 번째 사원수의 행과 두 번째 사원수의 열을 확인한다. 예를 들어 i에 j를 곱하려면 i의 행과 j의 열을 확인하여 답이 k임을 알 수 있다. j에 i를 곱하려면 j의 행과 i의 열을 확인하여 답이 -k임을 알 수 있다.

위 예제에서 볼 수 있듯이 사원수는 교환법칙을 만족하지 않는다. 즉, a * b != b * a인 a와 b가 존재한다. 그러나 결합법칙은 만족한다. 임의의 a, b, c에 대해 a * (b * c) = (a * b) * c가 성립한다.

사원수 앞의 음수 부호는 일반적인 방식으로 작용한다. 임의의 사원수 a와 b에 대해 -a * -b = a * b가 성립하고, -a * b = a * -b = -(a * b)가 성립한다.

i, j, k로 이루어진 문자열을 두 곳에서 나누어 세 부분 문자열을 만들었을 때, 가장 왼쪽 부분 문자열을 사원수 곱셈으로 계산한 결과가 i, 가운데 부분 문자열의 결과가 j, 오른쪽 부분 문자열의 결과가 k가 됨을 보여서 잘못 쓴 철자가 올바른 철자 ijk와 동등하다고 주장하려 한다. (예를 들어 jij는 j * i * j로 해석된다. j * i는 -k이고, -k * j는 i이므로 jij의 계산 결과는 i이다.) 이것이 가능하면 점수를 되찾을 수 있다. 그렇게 나누는 방법을 찾을 수 있는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ L ≤ 10000.

작은 데이터 세트

시간 제한: 240초. 1 ≤ X ≤ 10000. 1 ≤ L * X ≤ 10000.

큰 데이터 세트

시간 제한: 480초. 1 ≤ X ≤ $10^{12}$. 1 ≤ L * X ≤ $10^{16}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 정수 L과 X가 있는 한 줄과, 그 뒤에 오는 L개의 문자로 이루어진 한 줄로 구성된다. 모든 문자는 i, j, k 중 하나이다. 문자열에는 음수 부호, 1, 그 밖의 어떤 문자도 절대 포함되지 않는다는 점에 유의한다. 계산해야 할 문자열은 주어진 L개 문자로 이루어진 문자열을 X번 반복한 것이다. 예를 들어 L = 4, X = 3이고 주어진 문자열이 kiij라면, 입력 문자열은 kiijkiijkiij가 된다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 대로 문자열을 순서대로 i, j, k로 계산되는 세 부분으로 나눌 수 있는지에 따라 YES 또는 NO이다.

케이스 #1에서 문자열은 너무 짧아서 세 부분 문자열로 나눌 수 없다.

케이스 #2에서는 문자열을 i, j, k로 나누기만 하면 된다.

케이스 #3에서 문자열을 세 부분으로 나누는 유일한 방법은 k, j, i이며, 이는 조건을 만족하지 않는다.

케이스 #4에서 문자열은 jijijijijiji이다. 이를 jij (계산 결과가 i), iji (계산 결과가 j), jijiji (계산 결과가 k)로 나눌 수 있다.

케이스 #5에서는 부분 문자열을 어떻게 선택하더라도 그중 어느 것도 j나 k로 계산될 수 없다.