← 返回题目列表

Codeforces · 2200/C

C. 专业字符串

中文机器翻译题面 查看原题

AksLolCoding 正在长度为 $$$n$$$ 的字符串 $$$s$$$ 上玩游戏。最初,$$$s$$$ 仅包含小写拉丁字符。

在一轮中,AksLolCoding 可以选择任意一对整数 $$$(i,j)$$$,这样:

  • $$$1 \leq i \lt j \leq n$$$;
  • $$$s_i = s_j \neq *$$$;和
  • $$$s_k = *$$$ 对于所有 $$$i \lt k \lt j$$$。
如果不存在这样的$$$i,j$$$,则游戏结束。否则,AksLolCoding 设置 $$$s_i:=*$$$ 和 $$$s_j:=*$$$。

游戏结束后,当且仅当 $$$s$$$ 中的每个字符都等于 $$$*$$$ 时,AksLolCoding 获胜。确定 AksLolCoding 是否有可能获胜。

注意: $$$*$$$ 表示 ASCII 字符 42。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$),测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$),即字符串的长度。

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

所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

在其自己的行上输出每个测试用例的答案。如果AksLolCoding能获胜,则输出“是“(不带引号)。否则,输出“NO“(不带引号)。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。

示例

输入
复制

6
1
a
6
llmllm
6
uwuuwu
6
byebye
6
oooioi
12
siixxsevvenn

输出
复制

NO
YES
YES
NO
NO
YES

注意

在第一个测试用例中,可以证明 AksLolCoding 不可能获胜。

在第二个测试用例中,AksLolCoding 可以通过以下动作获胜: llmllm $$$\右箭头$$$ llm**m $$$\右箭头$$$ **米**米 $$$\右箭头$$$ ******

在第三个测试用例中,AksLolCoding 可以通过以下动作获胜: 呜呜呜 $$$\右箭头$$$ uw**wu $$$\右箭头$$$ u****u $$$\右箭头$$$ ******