D. Stuck in the Middle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a string $$$t$$$ of odd length $$$m$$$. Its middle character is the character at position $$$\dfrac{m+1}{2}$$$ (1-indexed).

We call $$$t$$$ centered if its middle character appears more than $$$\dfrac{m}{2}$$$ times in $$$t$$$.

You are given a string $$$s$$$ consisting of lowercase English letters.

Determine whether every odd-length substring of $$$s$$$ is centered.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$s$$$.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print YES if every odd-length substring of $$$s$$$ is centered. Otherwise, print NO.

Example
Input
3
8
centered
5
abbba
5
aabbz
Output
NO
YES
NO