Dijkstra (Large)

네덜란드의 계산기과학자 Edsger Dijkstra의 이름을 딴 최단 경로 알고리즘이 있다. 이 문제는 그 알고리즘과 관계가 없다.

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

두 사원수를 곱할 때는 앞 수의 행과 뒤 수의 열이 만나는 칸을 읽는다. 예를 들어 $i \times j$는 $k$이고, $j \times i$는 $-k$이다.

사원수의 곱셈에는 교환법칙이 성립하지 않는다. 즉 $a \times b \ne 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, 그 밖의 문자가 들어 있지 않다. 판정할 문자열은 주어진 길이 $L$ 문자열을 $X$번 이어 붙인 것이다. 예를 들어 $L = 4$, $X = 3$이고 주어진 문자열이 kiij이면 판정할 문자열은 kiijkiijkiij이다.

제한

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 문자열을 앞에서부터 $i$, $j$, $k$가 되는 세 조각으로 자를 수 있으면 YES, 그런 방법이 없으면 NO이다.

첫 번째 예제 입력의 다섯 케이스는 다음과 같다.

1번은 문자열이 너무 짧아 세 조각으로 나눌 수 없다.

2번은 i, j, k로 나누면 된다.

3번은 k, j, i로 나누는 방법밖에 없는데, 이 분할은 조건을 만족하지 않는다.

4번의 문자열은 jijijijijiji이다. $i$가 되는 jij, $j$가 되는 iji, $k$가 되는 jijiji로 나눌 수 있다.

5번은 어떻게 잘라도 $j$나 $k$가 되는 조각이 나오지 않는다.