CF1807C.Find and Replace

You are given a string $s$ consisting of lowercase Latin characters. In an operation, you can take a character and replace all occurrences of this character with $\texttt{0}$ or replace all occurrences of this character with $\texttt{1}$.

Is it possible to perform some number of moves so that the resulting string is an alternating binary string$^{\dagger}$?

For example, consider the string $\texttt{abacaba}$. You can perform the following moves:

• Replace $\texttt{a}$ with $\texttt{0}$. Now the string is $\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\texttt{c}\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}$.
• Replace $\texttt{b}$ with $\texttt{1}$. Now the string is ${\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\texttt{c}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}$.
• Replace $\texttt{c}$ with $\texttt{1}$. Now the string is ${\texttt{0}}{\texttt{1}}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}{\texttt{1}}{\texttt{0}}$. This is an alternating binary string.

$^{\dagger}$An alternating binary string is a string of $\texttt{0}$s and $\texttt{1}$s such that no two adjacent bits are equal. For example, $\texttt{01010101}$, $\texttt{101}$, $\texttt{1}$ are alternating binary strings, but $\texttt{0110}$, $\texttt{0a0a0}$, $\texttt{10100}$ are not.

给你一个由小写拉丁字母组成的字符串 $s$。在一次操作中，你可以选择一个字符，并将该字符的所有出现位置替换为 $\texttt{0}$，或将该字符的所有出现位置替换为 $\texttt{1}$。

是否可以通过若干次操作，使得最终得到的字符串是一个交替二进制字符串$^{\dagger}$？

例如，考虑字符串 $\texttt{abacaba}$。你可以执行以下操作：

• 将 $\texttt{a}$ 替换为 $\texttt{0}$。此时字符串变为 $\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}\texttt{c}\color{red}{\texttt{0}}\texttt{b}\color{red}{\texttt{0}}$。
• 将 $\texttt{b}$ 替换为 $\texttt{1}$。此时字符串变为 ${\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}\texttt{c}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}$。
• 将 $\texttt{c}$ 替换为 $\texttt{1}$。此时字符串变为 ${\texttt{0}}{\texttt{1}}{\texttt{0}}\color{red}{\texttt{1}}{\texttt{0}}{\texttt{1}}{\texttt{0}}$。这是一个交替二进制字符串。

$^{\dagger}$ 交替二进制字符串是指仅由 $\texttt{0}$ 和 $\texttt{1}$ 组成、且任意两个相邻字符均不相同的字符串。例如，$\texttt{01010101}$、$\texttt{101}$、$\texttt{1}$ 是交替二进制字符串，但 $\texttt{0110}$、$\texttt{0a0a0}$、$\texttt{10100}$ 不是。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2000$) — the length of the string $s$.

The second line of each test case contains a string consisting of $n$ lowercase Latin characters — the string $s$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$）—— 测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2000$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 —— 字符串 $s$。

For each test case, output "YES" (without quotes) if you can make the string into an alternating binary string, and "NO" (without quotes) otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

对于每个测试用例，如果可以将该字符串变为一个交替的二进制字符串，则输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

您可以以任意大小写形式输出答案（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为正确答案）。

The first test case is explained in the statement.

In the second test case, the only possible binary strings you can make are $\texttt{00}$ and $\texttt{11}$, neither of which are alternating.

In the third test case, you can make $\texttt{1}$, which is an alternating binary string.

第一个测试用例已在题目描述中进行了解释。

在第二个测试用例中，你能构造出的唯一二进制字符串是 $\texttt{00}$ 和 $\texttt{11}$，但它们都不是交替二进制字符串。

在第三个测试用例中，你可以构造出 $\texttt{1}$，这是一个交替二进制字符串。