Bessie vuole ordinare un array di interi con il proprio algoritmo. Ha un mucchio di $N$ interi $a_1,a_2,\dots,a_N$, con $(1 \leq N \leq 2\cdot 10^5)$ e $(1 \leq a_i \leq 10^{11})$, da mettere ordinati in un altro array. Trova ripetutamente il minimo del mucchio, lo rimuove e lo aggiunge in fondo all’array. Trovare il minimo tra $p$ interi richiede $p$ secondi.

Farmer John ha chiesto ad altre mucche di aiutarla, ma sono pigre, e Bessie ne approfitta. Divide gli interi nel proprio mucchio e in quello delle aiutanti. Elabora il proprio normalmente e assegna ogni intero dell’altro a un’aiutante diversa. La fattoria è grande, quindi può avere quante aiutanti vuole. Un’aiutante che riceve $a_i$ dorme $a_i$ secondi e aggiunge il suo intero in fondo all’array appena si sveglia. Se Bessie e un’aiutante aggiungono contemporaneamente, l’intero di Bessie viene prima perché è la capo. Più aiutanti con lo stesso intero ne aggiungono copie contemporaneamente.

Dividi gli interi affinché l’array finale sia ordinato e il tempo di ordinamento sia minimo.

Input

La prima riga contiene $T$, il numero di casi indipendenti ($1\le T\le 10$).

Ogni caso ha questo formato:

La prima riga contiene il numero di interi $N$ nell’array di Bessie.

La successiva contiene gli interi da ordinare, $a_1, a_2, \dots, a_N$. Lo stesso intero può apparire più volte.

La somma di $N$ su tutti i casi non supera $2\cdot 10^5$.

Output

Per ogni caso stampa su una nuova riga il tempo minimo di ordinamento con divisione ottimale.

Esempi

Input 1

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

Output 1

6
15
5
6

Nota

Nel primo esempio può assegnare $1,2$ alle aiutanti e tenere $4,5,10^{11}$.

Nel secondo è meglio ordinare tutto da sola. Assegnare $4$ a un’aiutante e tenere il resto non funziona: Bessie aggiungerebbe $17$ prima che l’aiutante aggiunga $4$.

Nel terzo può assegnare tutti gli interi alle aiutanti.

Nel quarto può assegnare $1,4,5$ alle aiutanti e tenere $2,5,100$.

Sottoproblemi

• Input 2: $N\le 16$
• Input 3–5: $N\le 150$
• Input 6–8: $\sum N\le 5000$
• Input 9–11: nessun vincolo aggiuntivo.

Autore del problema: Suhas Nagar