This is the easy version of the problem. The only difference between the easy and hard versions is what you are asked to find.

Yuki is a literary scholar!

She defines a string consisting only of lowercase letters as lovely if and only if:

• The number of characters that appear an odd number of times in the string is even.
• The number of characters that appear a positive even number of times in the string is odd.

For example, $\texttt{lovely}$ and $\texttt{milmon}$ are lovely, while $\texttt{dxqwq}$ and $\texttt{cocoly}$ are not lovely.

Now, Yuki has a string $s$ of length $n$ consisting only of lowercase letters. You need to help her determine whether $s$ is lovely.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t\ (1 \le t \le 10^5)$, representing the number of test cases.

For each test case:

• The first line contains a positive integer $n\ (1 \le n \le 5\cdot10^5)$.
• The second line contains a string $s$ of length $n$.

It is guaranteed that the string $s$ contains only lowercase letters, and the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output one line:

• If $s$ is lovely, output the string $\texttt{Yes}$.
• If $s$ is not lovely, output the string $\texttt{No}$.

The output is case-insensitive. For example, $\texttt{YES}$, $\texttt{yes}$, and $\texttt{yEs}$ will all be considered correct answers.

Examples

Input 1

8
5
hello
6
lovely
6
milmon
5
dxqwq
6
cocoly
6
qingyu
9
coffeezzz
6
byebye

Output 1

No
Yes
Yes
No
No
No
No
Yes

Note

For the first test case:

• In $\texttt{hello}$, the number of characters appearing an odd number of times is $3$, and the number of characters appearing a positive even number of times is $1$. Thus, $\texttt{hello}$ is not lovely.

For the second test case:

• In $\texttt{lovely}$, the number of characters appearing an odd number of times is $4$, and the number of characters appearing a positive even number of times is $1$. Thus, $\texttt{lovely}$ is lovely.