$n$ 個の頂点 $0$ から $n-1$ までを持つサイクルが与えられます。各 $0 \le i \le n-1$ について、頂点 $i$ と頂点 $((i + 1) \pmod n)$ の間には色 $c_i$ ($c_i = \text{R}$ または $\text{B}$) の無向辺が存在します。

すべての頂点のペア $(i, j)$ ($0 \le i < j \le n-1$) について、以下の条件が成り立つか判定してください。

• 頂点 $i$ と頂点 $j$ の間に回文経路が存在する。なお、経路は単純である必要はありません。形式的には、以下の条件を満たす数列 $p = [p_0, p_1, p_2, \dots, p_m]$ が存在しなければなりません。
  • $p_0 = i, p_m = j$
  • 各 $0 \le x \le m - 1$ について、$p_{x+1} = (p_x + 1) \pmod n$ または $p_{x+1} = (p_x - 1) \pmod n$ である。
  • $x + y = m - 1$ を満たす各 $0 \le x \le y \le m - 1$ について、頂点 $p_x$ と $p_{x+1}$ を結ぶ辺の色と、頂点 $p_y$ と $p_{y+1}$ を結ぶ辺の色は同じである。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^5$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、サイクル内の頂点数である整数 $n$ ($3 \le n \le 10^6$) が含まれます。 2行目には、各辺の色を表す長さ $n$ の文字列 $c$ ($c_i = \text{R}$ または $\text{B}$) が含まれます。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えないことが保証されています。

出力

各テストケースについて、任意の頂点ペアの間に回文経路が存在する場合は "YES" を、そうでない場合は "NO" を出力してください。

答えは大文字・小文字を区別しません。例えば、"yEs", "yes", "Yes", "YES" はすべて肯定的な回答として認識されます。

入出力例

入力 1

7
5
RRRRR
5
RRRRB
5
RBBRB
6
RBRBRB
6
RRBBRB
5
RBRBR
12
RRBRRBRRBRRB

出力 1

YES
YES
YES
NO
NO
YES
NO

注記

最初のテストケースでは、任意の2頂点間に回文経路が存在することが容易に示せます。

2番目のテストケースでは、任意の2頂点間に、赤色の辺のみを用いた回文経路が存在します。

3番目のテストケースでは、サイクルは $0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0$ となっています。例として $(i, j) = (0, 3)$ をとると、$0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0 \xrightarrow{\text{B}} 4 \xrightarrow{\text{R}} 3$ は回文経路です。したがって、$(i, j) = (0, 3)$ に対して条件が成り立ちます。

4番目のテストケースでは、$(i, j) = (0, 2)$ のとき、回文経路は存在しません。