Coins

Problem Description

There are $n$ people playing a game, where $i-$th person has $a_i$ coins. In each round, they randomly choose two players. Then the first one should give one coin to the second. If someone leaves no coin after that, he leaves the game and the rest players continue the game until a player owns all the coins. Foreverlasting wants to know the expected number of rounds.

Input

The first line contains integer $t\ (1 \leq t \leq 10^2)$ --- the number of test cases. For each of the next $t$ test cases, the format is: The first line contains an integer $n\ (2\leq n\leq 10^5)$, representing the number of people. The next line contains $n$ integers $a_i\ (1\leq a_i\leq 10^6)$, representing the number of coins that each person has. (请不要使用 scanf 进行读入)

Output

For each case, output the expected number of rounds. The answer is guaranteed to be an integer.

Sample Input

1
3
1 1 1

Sample Output

3

Source

2023“钉耙编程”中国大学生算法设计超级联赛（9）