3비트 컴퓨터

바이트랜드 왕국의 과학자들이 3비트 컴퓨터(Three Bit Computer, TBC)라는 새로운 기계를 만들고 있습니다. 이 기계를 작동시키려면 먼저 메모리를 초기화하는 방법에 관한 문제를 해결해야 하며, 과학자들이 여러분에게 도움을 요청했습니다.

현재 TBC에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 메모리 칸이 있습니다. 각 칸은 초기화되지 않은 상태이거나, 세 가지 값 $a$, $b$, $c$ 중 하나를 가집니다. 이 기계는 다음 두 가지 초기화 연산을 지원합니다.

• 연속한 두 칸 $i$번과 $i+1$번($1 \le i < n$)이 모두 초기화되지 않은 상태일 때, 두 칸을 서로 다른 두 값으로 설정할 수 있습니다.
• 연속한 두 칸 중 하나는 초기화되지 않았고 다른 하나는 값 $x$를 가지고 있을 때, 두 칸을 모두 $x$가 아닌 두 값(즉 $\{a, b, c\} \setminus \{x\}$의 두 값을 어떤 순서로든)으로 설정할 수 있습니다.

예를 들어 $n = 4$일 때, 초기화되지 않은 칸을 $u$로 나타내면 다음과 같은 초기화가 가능합니다.

$uuuu \rightarrow uuab \rightarrow ucbb \rightarrow babb$

모든 칸이 최종적으로 가져야 할 목표 패턴이 주어질 때, 완전히 초기화되지 않은 메모리에서 시작하여 그 패턴과 정확히 일치하도록 초기화할 수 있는지 판별하는 프로그램을 작성하세요.

첫째 줄에 목표 패턴의 개수 $N$($1 \le N \le 10$)이 주어집니다.

각 패턴은 두 줄로 설명됩니다.

• 첫째 줄에는 해당 패턴의 메모리 칸 수 $\ell_i$($1 \le \ell_i \le 100\,000$)가 주어집니다.
• 둘째 줄에는 문자 $a$, $b$, $c$로만 이루어진 길이 $\ell_i$의 문자열, 즉 목표 패턴이 주어집니다.

각 패턴에 대해 입력에 주어진 순서대로 한 줄씩, 총 $N$개의 줄을 출력합니다. $i$번째 패턴에 대해 메모리를 그 패턴으로 초기화할 수 있으면 YES를, 그렇지 않으면 NO를 출력합니다.