B. Игры с монетками
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На столе лежат $$$n$$$ монет, образующих круг, и каждая монета лежит либо лицевой стороной вверх, либо лицевой стороной вниз. Алиса и Боб играют в игру, где они ходят по очереди, причем Алиса ходит первой.

В ходе каждой операции игрок выбирает монету, лежащую лицевой стороной вверх, убирает ее, и переворачивает две соседние монеты. Если перед операцией осталось две монеты, то одна убирается, а вторая не переворачивается (так как ее пришлось бы переворачивать дважды). Если перед операцией осталась только одна монета, то ни одна монета не переворачивается. Если перед операцией нет ни одной монеты, лежащей лицевой стороной вверх, игрок проигрывает.

Определите, кто победит в игре, если оба будут играть оптимально. Можно доказать, что игра закончится за конечное число операций, и один из них выиграет.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно положительное целое число $$$n$$$ ($$$1 \leq n \leq 100$$$), обозначающее количество монет.

Во второй строке каждого набора входных данных содержится строка $$$s$$$ длины $$$n$$$, состоящая из символов «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$$$ становится пустой.
  • Боб теперь не может выбрать ни одной монеты и проигрывает.

Можно показать, что Боб всегда будет проигрывать, если оба играют оптимально.