311345: CF1972B. Coin Games

B. Coin Gamestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $n$ coins on the table forming a circle, and each coin is either facing up or facing down. Alice and Bob take turns to play the following game, and Alice goes first.

In each operation, the player chooses a facing-up coin, removes the coin, and flips the two coins that are adjacent to it. If (before the operation) there are only two coins left, then one will be removed and the other won't be flipped (as it would be flipped twice). If (before the operation) there is only one coin left, no coins will be flipped. If (before the operation) there are no facing-up coins, the player loses.

Decide who will win the game if they both play optimally. It can be proved that the game will end in a finite number of operations, and one of them will win.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100$). The description of the test cases follows.

The first line of each test case contains only one positive integer $n$ ($1 \leq n \leq 100$), representing the number of the coins.

A string $s$ of length $n$ follows on the second line of each test case, containing only "U" and "D", representing that each coin is facing up or facing down.

Output

For each test case, print "YES" if Alice will win the game, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

3
5
UUDUD
5
UDDUD
2
UU

Output

YES
NO
NO

Note

In the first test case, the game may go as follows.

• Alice chooses the first coin and $s$ becomes "DDUU".
• Bob chooses the last coin and $s$ becomes "UDD".
• Alice chooses the first coin and $s$ becomes "UU".
• Bob chooses the first coin and $s$ becomes "U".
• Alice chooses the only coin and $s$ becomes empty.
• Bob can't choose any coin now, and he loses the game.

It can be proved that Bob will always lose if they both play optimally.

题目大意：
这是一道关于硬币游戏的题目。有n枚硬币围成一圈，每枚硬币要么正面朝上，要么反面朝上。爱丽丝和鲍勃轮流进行游戏，爱丽丝先手。每次操作，玩家选择一枚正面朝上的硬币，移除这枚硬币，并翻转它两侧的硬币。如果操作前只剩下两枚硬币，那么将移除一枚，另一枚不会翻转（因为它会被翻转两次）。如果操作前只剩下一枚硬币，没有硬币会被翻转。如果操作前没有正面朝上的硬币，该玩家就输了。游戏将以有限次的操作结束，并且其中一人将会获胜。需要判断如果双方都采取最优策略，谁将会赢得游戏。

输入数据格式：
输入包含多个测试用例。第一行包含测试用例的数量t（1≤t≤100）。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个正整数n（1≤n≤100），表示硬币的数量。
第二行是一个长度为n的字符串s，只包含“U”（正面朝上）和“D”（正面朝下），表示每枚硬币的状态。

输出数据格式：
对于每个测试用例，如果爱丽丝将会赢得游戏，则输出“YES”，否则输出“NO”。
输出答案时大小写不敏感，例如，“yEs”、“yes”、“Yes”和“YES”都会被识别为肯定回答。

示例：
输入：
3
5
UUDUD
5
UDDUD
2
UU
输出：
YES
NO
NO

注意：
在第一个测试案例中，游戏可能按照以下步骤进行：
- 爱丽丝选择第一枚硬币，s变为"DDUU"。
- 鲍勃选择最后一枚硬币，s变为"UDD"。
- 爱丽丝选择第一枚硬币，s变为"UU"。
- 鲍勃选择第一枚硬币，s变为"U"。
- 爱丽丝选择唯一的一枚硬币，s变为空。
- 鲍勃现在不能选择任何硬币，他输了游戏。
可以证明，如果双方都采取最优策略，鲍勃总是会输。题目大意： 这是一道关于硬币游戏的题目。有n枚硬币围成一圈，每枚硬币要么正面朝上，要么反面朝上。爱丽丝和鲍勃轮流进行游戏，爱丽丝先手。每次操作，玩家选择一枚正面朝上的硬币，移除这枚硬币，并翻转它两侧的硬币。如果操作前只剩下两枚硬币，那么将移除一枚，另一枚不会翻转（因为它会被翻转两次）。如果操作前只剩下一枚硬币，没有硬币会被翻转。如果操作前没有正面朝上的硬币，该玩家就输了。游戏将以有限次的操作结束，并且其中一人将会获胜。需要判断如果双方都采取最优策略，谁将会赢得游戏。 输入数据格式： 输入包含多个测试用例。第一行包含测试用例的数量t（1≤t≤100）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个正整数n（1≤n≤100），表示硬币的数量。 第二行是一个长度为n的字符串s，只包含“U”（正面朝上）和“D”（正面朝下），表示每枚硬币的状态。 输出数据格式： 对于每个测试用例，如果爱丽丝将会赢得游戏，则输出“YES”，否则输出“NO”。 输出答案时大小写不敏感，例如，“yEs”、“yes”、“Yes”和“YES”都会被识别为肯定回答。 示例： 输入： 3 5 UUDUD 5 UDDUD 2 UU 输出： YES NO NO 注意： 在第一个测试案例中，游戏可能按照以下步骤进行： - 爱丽丝选择第一枚硬币，s变为"DDUU"。 - 鲍勃选择最后一枚硬币，s变为"UDD"。 - 爱丽丝选择第一枚硬币，s变为"UU"。 - 鲍勃选择第一枚硬币，s变为"U"。 - 爱丽丝选择唯一的一枚硬币，s变为空。 - 鲍勃现在不能选择任何硬币，他输了游戏。 可以证明，如果双方都采取最优策略，鲍勃总是会输。