Необходимо написать программу на питоне

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

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

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

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

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

Во второй строке каждого набора входных данных содержится строка s длины n , состоящая из символов «U» и «D», обозначающие, что монета лежит лицевой стороной вверх или лицевой стороной вниз, соответственно.

Выходные данные
Для каждого набора входных данных выведите «YES», если Алиса выиграет игру, и «NO» в противном случае.