Three Bit Computer

The scientists of the Kingdom of Byteland are building a new machine called the Three Bit Computer (TBC). Before it can run, they must solve a problem about how its memory is initialized, and they have asked for your help.

The current TBC has $n$ memory cells, numbered from $1$ to $n$. Every cell is either uninitialized or holds one of the three values $a$, $b$, or $c$. The machine supports exactly two initialization operations:

• Take two consecutive cells $i$ and $i+1$ (with $1 \le i < n$) that are both uninitialized, and set them to two different values.
• Take two consecutive cells where one is uninitialized and the other already holds a value $x$, and set both of them to the two values different from $x$ (that is, the two values of $\{a, b, c\} \setminus \{x\}$, in either order).

For example, with $n = 4$ the following initialization is possible (writing $u$ for an uninitialized cell):

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

Given a target pattern that every cell must end up holding, write a program that decides whether the memory can be initialized to that exact pattern, starting from a completely uninitialized memory.

The first line contains a single integer $N$ ($1 \le N \le 10$), the number of target patterns.

Each pattern is described on two lines:

• the first line contains an integer $\ell_i$ ($1 \le \ell_i \le 100\,000$), the number of memory cells for that pattern;
• the second line contains a string of length $\ell_i$ consisting only of the letters $a$, $b$, and $c$ — the target pattern itself.

Print $N$ lines, one per pattern in the given order. For the $i$-th pattern print YES if the memory can be initialized to that pattern, or NO otherwise.