給你一個包含 $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$），代表環上的頂點數量。

第二行包含一個長度為 $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

說明

在第一個測試案例中，很容易證明任意兩頂點間皆存在迴文路徑。

在第二個測試案例中，對於任意兩頂點，皆存在一條僅由紅色邊組成的迴文路徑。

在第三個測試案例中，環的結構如下：$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)$ 成立。

在第四個測試案例中，當 $(i, j) = (0, 2)$ 時，不存在迴文路徑。