桌面上排成一个圆圈放着 $n$ 枚硬币，每枚硬币要么正面朝上，要么背面朝上。Alice 和 Bob 轮流玩以下游戏，Alice 先手。

在每次操作中，玩家选择一枚正面朝上的硬币，将其移除，并翻转与其相邻的两枚硬币。如果（操作前）只剩下两枚硬币，则其中一枚会被移除，而另一枚不会被翻转（因为它会被翻转两次）。如果（操作前）只剩下一枚硬币，则不会翻转任何硬币。如果（操作前）没有正面朝上的硬币，则当前玩家输掉游戏。

确定如果双方都采取最优策略，谁将赢得游戏。可以证明，游戏将在有限次操作内结束，且其中一人必胜。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。接下来是测试用例的描述。

每个测试用例的第一行仅包含一个正整数 $n$ ($1 \le n \le 100$)，表示硬币的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅包含 "U" 和 "D"，表示每枚硬币是正面朝上（"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$ 变为空。
• Bob 现在无法选择任何硬币，因此输掉了游戏。

可以证明，如果双方都采取最优策略，Bob 注定会输。