$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 R 1 B 2 B 3 R 4 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)$인 경우, 팰린드롬 경로는 존재하지 않는다.