There are n people playing a game, where i−th person has ai 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. F wants to know the expected number of rounds.
输入格式
The first line contains integer t (1 ≤ t ≤ 102) — the number of test cases.
For each of the next t test cases, the format is:
The first line contains an integer n (2 ≤ n ≤ 105), representing the number of people.
The next line contains n integers ai (1 ≤ ai ≤ 106), representing the number of coins that each person has.
输出格式
For each case, output the expected number of rounds.