Problem Description

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\le T\le 100$), denoting the number of test cases.

For each test case, the first line contains an integer $n$ ($1\le n\le 5\cdot 10^5$).

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

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

Output

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

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

YES
NO
YES