Bạn được cho một chu trình với $n$ đỉnh được đánh số từ $0$ đến $n - 1$. Với mỗi $0 \le i \le n - 1$, có một cạnh vô hướng giữa đỉnh $i$ và đỉnh $((i + 1) \pmod n)$ với màu $c_i$ ($c_i = \text{R}$ hoặc $\text{B}$).

Xác định xem điều kiện sau có thỏa mãn với mọi cặp đỉnh $(i, j)$ ($0 \le i < j \le n - 1$) hay không:

• Tồn tại một đường đi đối xứng (palindrome route) giữa đỉnh $i$ và đỉnh $j$. Lưu ý rằng đường đi này không nhất thiết phải là đường đi đơn. Một cách hình thức, phải tồn tại một dãy $p = [p_0, p_1, p_2, \dots, p_m]$ sao cho:
  • $p_0 = i, p_m = j$;
  • Với mỗi $0 \le x \le m - 1$, $p_{x+1} = (p_x + 1) \pmod n$ hoặc $p_{x+1} = (p_x - 1) \pmod n$;
  • Với mỗi $0 \le x \le y \le m - 1$ thỏa mãn $x + y = m - 1$, cạnh giữa $p_x$ và $p_{x+1}$ có cùng màu với cạnh giữa $p_y$ và $p_{y+1}$.

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều bộ dữ liệu. Dòng đầu tiên chứa số lượng bộ dữ liệu $t$ ($1 \le t \le 10^5$) — số lượng bộ dữ liệu. Tiếp theo là mô tả của các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa một số nguyên $n$ ($3 \le n \le 10^6$) — số lượng đỉnh trong chu trình.

Dòng thứ hai chứa một chuỗi $c$ có độ dài $n$ ($c_i = \text{R}$ hoặc $\text{B}$) — màu của mỗi cạnh.

Đảm bảo rằng tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra "YES" (không có dấu ngoặc kép) nếu tồn tại một đường đi đối xứng giữa bất kỳ cặp nút nào, và "NO" (không có dấu ngoặc kép) nếu ngược lại.

Bạn có thể xuất câu trả lời ở bất kỳ định dạng chữ hoa hay chữ thường nào. Ví dụ, các chuỗi "yEs", "yes", "Yes", và "YES" đều được công nhận là phản hồi khẳng định.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

YES
YES
YES
NO
NO
YES
NO

Ghi chú

Trong bộ dữ liệu đầu tiên, dễ dàng thấy rằng tồn tại một đường đi đối xứng giữa bất kỳ hai đỉnh nào.

Trong bộ dữ liệu thứ hai, với bất kỳ hai đỉnh nào, luôn tồn tại một đường đi đối xứng chỉ sử dụng các cạnh màu đỏ.

Trong bộ dữ liệu thứ ba, chu trình như sau: $0 \xrightarrow{\text{R}} 1 \xrightarrow{\text{B}} 2 \xrightarrow{\text{B}} 3 \xrightarrow{\text{R}} 4 \xrightarrow{\text{B}} 0$. Lấy $(i, j) = (0, 3)$ làm ví dụ, khi đó $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$ là một đường đi đối xứng. Do đó, điều kiện thỏa mãn với $(i, j) = (0, 3)$.

Trong bộ dữ liệu thứ tư, khi $(i, j) = (0, 2)$, không tồn tại đường đi đối xứng nào.