1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import math

def minimum_players(n, a):
    total_games = sum(a)  # Suma rozgrywek
    # Zakładając, że musimy znaleźć minimalną liczbę graczy, to:
    # minimalna liczba graczy musi spełniać warunek, że wybieramy trójki
    # w taki sposób, żeby rozgrywki się zgadzały.
    for players in range(3, 1000000):  # Sprawdzamy od 3 graczy wzwyż
        # Liczba możliwych trójek z `players` graczy
        total_combinations = math.comb(players, 3)
        if total_combinations >= total_games:
            if (sum(a) / len(a)) % 1 == 0 and sum(a) / len(a) == a[0] and len(a) > 1:
                return players + 1
            else:
                return players
    return -1  # Jeśli nic nie znajdziemy (teoretycznie nie wystąpi w tym zadaniu)

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    print(minimum_players(len(a), a))