N. Balanced Distinct Coloring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of length $$$n$$$. You may color every position of the array either black or white. Let $$$D_B$$$ be the number of distinct values that appear in at least one black position, and let $$$D_W$$$ be the number of distinct values that appear in at least one white position.

Your task is to determine whether there exists a coloring such that $$$D_B = D_W$$$.

Input

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

Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array.

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 there exists a coloring such that $$$D_B = D_W$$$. Otherwise, print NO.

You may print each letter in any case.

Example
Input
5
1
1
4
1 2 3 4
6
1 1 2 3 4 5
3
2 2 2
7
1 2 1 3 4 5 6
Output
NO
YES
YES
YES
YES
Note

The colorings mentioned below are only explanations for the sample answers. They should not be printed.

In the first test case, the only value would appear in exactly one color, so the two numbers of distinct values cannot be equal.

In the second test case, there are $$$4$$$ distinct values. For example, values $$$1$$$ and $$$2$$$ can be colored black, and values $$$3$$$ and $$$4$$$ can be colored white. Then $$$D_B=D_W=2$$$.

In the third test case, there are $$$5$$$ distinct values and the value $$$1$$$ appears twice. For example, color the first occurrence of $$$1$$$ black, the second occurrence of $$$1$$$ white, values $$$2$$$ and $$$3$$$ black, and values $$$4$$$ and $$$5$$$ white. Then both colors contain exactly $$$3$$$ distinct values.

In the fourth test case, all positions contain value $$$2$$$. Since there is more than one occurrence, at least one occurrence can be colored black and at least one occurrence can be colored white. Then $$$D_B=D_W=1$$$.