Archiwum zadań programistycznych WWSI

Twoim zadaniem jest określić maksymalną możliwą długość ciągu wygenerowanego poprzez wielokrotne użycie n różnych elementów otrzymanych na wejściu. Ciąg musi spełniać wyłącznie jeden warunek: dowolne kolejne n pozycji ciągu musi składać się z dokładnie n różnych elementów.

Aby nieco dokładniej wyjaśnić dosyć zawile opisany problem poniżej przedstawione zostało rozwiązanie drugiego zestawu z danych przykładowych: 3 3 2 1 (jako elementy ciągu wyłącznie dla zilustrowania problemu użyte zostały liter A, B oraz C).

Dysponując trzema literami A, dwoma literami B oraz jedną literą C, najdłuższy ciąg spełniający wymaganie aby dowolne kolejne trzy pozycje składały się z dokładnie trzech różnych elementów to: ABCAB, odpowiedź zatem wynosi 5.

Wejście

W pierwszej linii wejścia znajduje się liczba t (1 ≤ t ≤ 500) określająca ilość zestawów danych. Każdy zestaw mieści się w jednej linii i składa się z liczby n (2 ≤ n ≤ 1000) określającej ile różnych elementów występować będzie w ciągu i następujących po niej n liczb (i-ta liczba określa ile i-tych elementów jest do dyspozycji).

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego zestawu danych wypisać jedną liczbę określającą maksymalną możliwą długość ciągu spełniającego wymóg opisany w treści zadania.

Przykład

Wejście:

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

Wyjście:

11
5
5