Bessie chce posortować tablicę liczb całkowitych własnym algorytmem. Ma stos $N$ liczb $a_1,a_2,\dots,a_N$, gdzie $(1 \leq N \leq 2\cdot 10^5)$ i $(1 \leq a_i \leq 10^{11})$, które umieści w osobnej tablicy w kolejności posortowanej. Wielokrotnie znajduje minimum stosu, usuwa je i dodaje na koniec tablicy. Znalezienie minimum wśród $p$ liczb zajmuje $p$ sekund.

Farmer John polecił innym krowom pomagać, ale są leniwe, więc Bessie to wykorzystuje. Dzieli liczby na swój stos i stos pomocnic. Swój przetwarza zwykłym algorytmem, a każdą liczbę z drugiego daje innej pomocnicy. Farma jest duża, więc może mieć dowolnie wiele pomocnic. Pomocnica otrzymująca $a_i$ śpi $a_i$ sekund i natychmiast po przebudzeniu dodaje liczbę na koniec tablicy. Jeśli Bessie i pomocnica dodają jednocześnie, liczba Bessie jest pierwsza, bo jest liderką. Pomocnice z tą samą liczbą dodają jej kopie jednocześnie.

Podziel liczby tak, aby końcowa tablica była posortowana, a czas sortowania minimalny.

Wejście

Pierwszy wiersz zawiera $T$, liczbę niezależnych przypadków ($1\le T\le 10$).

Każdy przypadek ma następujący format:

Pierwszy wiersz zawiera liczbę liczb $N$ w tablicy Bessie.

Następny zawiera sortowane liczby $a_1, a_2, \dots, a_N$. Ta sama liczba może wystąpić wielokrotnie.

Suma $N$ po wszystkich przypadkach nie przekracza $2\cdot 10^5$.

Wyjście

Dla każdego przypadku wypisz w nowym wierszu minimalny czas sortowania przy optymalnym podziale.

Przykład

Wejście 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

Wyjście 1

6
15
5
6

Uwagi

W pierwszym przykładzie może dać $1,2$ pomocnicom i zachować $4,5,10^{11}$.

W drugim najlepiej sortować wszystko samodzielnie. Danie $4$ pomocnicy i zachowanie reszty nie działa: Bessie doda $17$, zanim pomocnica doda $4$.

W trzecim może dać wszystkie liczby pomocnicom.

W czwartym może dać $1,4,5$ pomocnicom i zachować $2,5,100$.

Podzadania

• Wejście 2: $N\le 16$
• Wejścia 3–5: $N\le 150$
• Wejścia 6–8: $\sum N\le 5000$
• Wejścia 9–11: bez dodatkowych ograniczeń.

Autor zadania: Suhas Nagar