Equalize the Array

You are given an array $a$ consisting of $n$ integers.

In one move, you can choose a positive integer $x$, such that $x$ is one of the modes of the array, then add $1$ to each $x$ in $a$.

An integer $x$ is a mode of an array $a$ if and only if $x$ appears most frequently in $a$. Note that an array may have multiple modes (e.g. $2,3$ are both the modes of $[2,2,1,3,3]$).

Find out if it is possible to get an array that all elements in it are equal through several (possibly zero) such moves.

Input

The first line contains a single integer $T \: (1 \leq T \leq 100)$, denoting the number of test cases.

For each test case, the first line contains an integer $n \: (1 \leq n \leq 10^6)$.

The next line contains $n$ integers. The $i$-th number denotes $a_i \: (1 \leq a_i \leq n)$.

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

Output

For each test case, output a string. If it is possible, output YES; otherwise, output NO.

Example

3
5
1 2 3 4 5
5
4 4 1 4 4
4
2 2 2 2

YES
NO
YES