B. The String Only Contains a, b, and c
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting only of the letters a, b, and c. You want to split $$$s$$$ into contiguous substrings such that the average number of distinct characters over all the substrings is exactly $$$2$$$. For example, here is one way you could split up the string abcabaaaaccbabcc (along with the number of distinct characters in each section):

Since the average number of characters in each substring is $$$\frac{3 + 1 + 3 + 1}{4} = 2$$$, this is a suitable way to split up the string.

Input

Each test consists of multiple test cases.

The first line of input 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 10^5$$$) — the length of $$$s$$$. The next line of each test case contains a single string of length $$$n$$$ consisting only of the letters a, b, and c — the string $$$s$$$.

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

Output

For each test case, print YES if there is a valid way to split up the string $$$s$$$, and NO otherwise. You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).

Example
Input
4
16
abcabaaaaccbabcc
6
abcabc
5
aaaaa
2
cb
Output
YES
YES
NO
YES
Note

The first test case corresponds to the image above.

In the second test case, the string $$$s=$$$abcabc can be divided up into ab, ca, and bc, each of which contains two distinct characters.

In the third test case, we can prove that there is no suitable partition of $$$s$$$.

In the fourth test case, we can include all of $$$s$$$ in one substring, since there are two distinct characters in cb.