You are given a cycle with $$$n$$$ vertices numbered from $$$0$$$ to $$$n-1$$$. For each $$$0\le i\le n-1$$$, there is an undirected edge between vertex $$$i$$$ and vertex $$$((i+1)\bmod n)$$$ with the color $$$c_i$$$ ($$$c_i=\texttt{R}$$$ or $$$\texttt{B}$$$).

Determine whether the following condition holds for every pair of vertices $$$(i,j)$$$ ($$$0\le i \lt j\le n-1$$$):

There exists a palindrome route between vertex $$$i$$$ and vertex $$$j$$$. Note that the route may not be simple. Formally, there must exist a sequence $$$p=[p_0,p_1,p_2,\ldots,p_m]$$$ such that:
- $$$p_0=i$$$, $$$p_m=j$$$;
- For each $$$0\leq x\le m-1$$$, either $$$p_{x+1}=(p_x+1)\bmod n$$$ or $$$p_{x+1}=(p_{x}-1)\bmod n$$$;
- For each $$$0\le x\le y\le m-1$$$ satisfying $$$x+y=m-1$$$, the edge between $$$p_x$$$ and $$$p_{x+1}$$$ has the same color as the edge between $$$p_y$$$ and $$$p_{y+1}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$3\leq n\leq10^6$$$) — the number of vertices in the cycle.

The second line contains a string $$$c$$$ of length $$$n$$$ ($$$c_i=\texttt{R}$$$ or $$$\texttt{B}$$$) — the color of each edge.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print "YES" (without quotes) if there is a palindrome route between any pair of nodes, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note

In the first test case, it is easy to show that there is a palindrome route between any two vertices.

In the second test case, for any two vertices, there exists a palindrome route with only red edges.

In the third test case, the cycle is as follows: $$$0\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}3\color{red}{\overset{\texttt{R}}{\longleftrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longleftrightarrow}}0$$$. Take $$$(i,j)=(0,3)$$$ as an example, then $$$0\color{red}{\overset{\texttt{R}}{\longrightarrow}}1\color{blue}{\overset{\texttt{B}}{\longrightarrow}}2\color{blue}{\overset{\texttt{B}}{\longrightarrow}}3\color{red}{\overset{\texttt{R}}{\longrightarrow}}4\color{blue}{\overset{\texttt{B}}{\longrightarrow}}0\color{blue}{\overset{\texttt{B}}{\longrightarrow}}4\color{red}{\overset{\texttt{R}}{\longrightarrow}}3$$$ is a palindrome route. Thus, the condition holds for $$$(i,j)=(0,3)$$$.

In the fourth test case, when $$$(i,j)=(0,2)$$$, there does not exist a palindrome route.

Palindrome Everywhere

Examples