给您一个由小写拉丁字符组成的字符串 $$$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}$$$ 不是。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2000$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含一个由 $$$n$$$ 小写拉丁字符组成的字符串 - 字符串 $$$s$$$。
输出
对于每个测试用例,如果可以将字符串变成交替的二进制字符串,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
8 7 abacaba 2 aa 1 y 4 bkpt 6 ninfia 6 banana 10 codeforces 8 testcase
输出 #1
YES NO YES YES NO YES NO NO
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,唯一可能的二进制字符串是 $$$\texttt{00}$$$ 和 $$$\texttt{11}$$$,它们都不是交替的。
在第三个测试用例中,您可以创建 $$$\texttt{1}$$$,它是一个交替的二进制字符串。