桌子上有 $$$n$$$ 硬币,围成一个圆圈,每个硬币要么朝上,要么朝下。 Alice 和 Bob 轮流玩下面的游戏,Alice 先玩。
在每次操作中,玩家选择一枚面朝上的硬币,取出该硬币,然后翻转与其相邻的两枚硬币。如果(在操作之前)只剩下两枚硬币,那么一枚将被移除,而另一枚将不会被翻转(因为它会被翻转两次)。如果(操作前)只剩下一枚硬币,则不会翻转任何硬币。如果(在操作之前)没有面朝上的硬币,玩家就输了。
如果双方都发挥最佳,决定谁将赢得比赛。可以证明,游戏会在有限次数的操作中结束,其中一次获胜。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\le t\le 100$$$)。测试用例的描述如下。
每个测试用例的第一行只包含一个正整数$$$n$$$ ($$$1 \leq n \leq 100$$$),代表硬币的数量。
每个测试用例的第二行后面跟着一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含“U”和“D”,表示每个硬币朝上或朝下。
输出
对于每个测试用例,如果 Alice 将赢得游戏,则打印“YES”,否则打印“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
3 5 UUDUD 5 UDDUD 2 UU
输出 #1
YES NO NO
注意
在第一个测试用例中,游戏可能会如下进行。
- Alice 选择第一个硬币,$$$s$$$ 变成“DDUU”。
- Bob 选择最后一个硬币,$$$s$$$ 变成“UDD”。
- Alice 选择第一个硬币,$$$s$$$ 变成“UU”。
- Bob 选择第一个硬币,$$$s$$$ 变成“U”。
- Alice 选择唯一的硬币,$$$s$$$ 变空。
- 鲍勃现在无法选择任何硬币,他输了游戏。
可以证明,如果他们都发挥最佳,鲍勃总是会输。