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$$$。
游戏结束后,当且仅当 $$$s$$$ 中的每个字符都等于 $$$*$$$ 时,AksLolCoding 获胜。确定 AksLolCoding 是否有可能获胜。
注意: $$$*$$$ 表示 ASCII 字符 42。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$),测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5000$$$),即字符串的长度。
每个测试用例的第二行包含一个由小写拉丁字符组成的字符串 $$$s$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
在其自己的行上输出每个测试用例的答案。如果AksLolCoding能获胜,则输出“是“(不带引号)。否则,输出“NO“(不带引号)。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
61a6llmllm6uwuuwu6byebye6oooioi12siixxsevvenn
输出复制
NOYESYESNONOYES
注意
在第一个测试用例中,可以证明 AksLolCoding 不可能获胜。
在第二个测试用例中,AksLolCoding 可以通过以下动作获胜: llmllm $$$\右箭头$$$ llm**m $$$\右箭头$$$ **米**米 $$$\右箭头$$$ ******
在第三个测试用例中,AksLolCoding 可以通过以下动作获胜: 呜呜呜 $$$\右箭头$$$ uw**wu $$$\右箭头$$$ u****u $$$\右箭头$$$ ******