D. Разноцветная печать
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан ряд из $$$n$$$ клеток, изначально каждая клетка белого цвета. С помощью печати, вы можете покрасить любые две соседние клетки так, что одна из них становится красной, а другая синей. Печать можно поворачивать, то есть вы можете покрасить клетки обоими способами: как $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$$$, так и $$$\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$$$.

Во время каждого применения печати она должна находиться над заданными $$$n$$$ клетками (то есть она не может частично находится вне этих клеток). На одну и ту же клетку печать может быть применена многократно. Каждое следующее применение печати перекрашивает обе клетки, которые под печатью.

Например, один из способов сделать рисунок $$$\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$$$ выглядит так: $$$\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}$$$. Здесь $$$\texttt{W}$$$, $$$\color{red}{\texttt{R}}$$$, и $$$\color{blue}{\texttt{B}}$$$ обозначают белую, красную, и синюю клетки, соответственно, а клетки, к которым приложили печать подчёркнуты.

Дан конечный рисунок. Возможно ли сделать его, использовав печать ноль или больше раз?

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длина рисунка.

Вторая строка каждого набора содержит строку $$$s$$$ — рисунок, который нужно получить. Гарантируется, что длина $$$s$$$ равна $$$n$$$ и $$$s$$$ состоит только из символов $$$\texttt{W}$$$, $$$\texttt{R}$$$, и $$$\texttt{B}$$$, обозначающие белую, красную, и синюю клетки, соответственно.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Выведите $$$t$$$ строк, каждая из которых содержит ответ на соответствующий набор входных данных. В качестве ответа выведите «YES», если возможно получить рисунок, используя печать, и «NO» иначе.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
12
5
BRBBW
1
B
2
WB
2
RW
3
BRB
3
RBB
7
WWWWWWW
9
RBWBWRRBW
10
BRBRBRBRRB
12
BBBRWWRRRWBR
10
BRBRBRBRBW
5
RBWBW
Выходные данные
YES
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
NO
Примечание

Первый пример разобран в условии.

Во втором, третьем и четвёртом примерах невозможно покрасить одну клетку, так что ответ «NO».

В пятом примере можно поркасить следующим образом: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}$$$.

В шестом примере можно поркасить следующим образом: $$$\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}$$$.

В седьмом примере печать не нужно использовать вовсе.