POLSKI SPOJ

Być może potrzebujesz najpierw przeczytać zadanie Wiek segmentolka.

Szczęśliwy Jaś potrafi już wyznaczać maksymalny możliwy wiek znalezionych nad stawem żyjątek. W szkole chwali się i opowiada kolegom, jak to wczoraj znalazł dużą kolonię segmentolków i rodzice pomogli mu obliczać, ile mogą mieć dni. "Niektóre żyjątka mogły być już baaardzo stare!" - mówił z podekscytowaniem. Zaciekawieni chłopcy postanowili po lekcjach udać się nad pobliski staw i pooglądać różnej wielkości segmentolki. Ich rozmowie przysłuchiwała się Małgosia. Również ona postanowiła pobiec z chłopcami nad staw w poszukiwaniu tych ciekawych żyjątek. "Jakie piękne! Jakie duże!" - zachwycała się dziewczynka.

Jak to zwykle bywa z dziewczynkami, Małgosia miała troszkę inne spojrzenie na żyjątka niż jej koledzy. Zapytała: "A ile dni minimalnie mają te śliczne segmentolki?". Hmm... Tego chłopcy nie wiedzieli. I zaczęli liczyć. Liczyli i liczyli, ale wciąż doliczyć się nie mogli. Zrezygnowani i smutni wrócili do domu, postanowili znów poprosić o pomoc rodziców Jasia. Twoim zadaniem jest napisanie programu obliczającego minimalny wiek segmentolków.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą t - liczbę zestawów danych, których opisy występują kolejno po sobie. Każdy zestaw opisany jest przez jedną linię wejścia, składającą się z nieujemnych liczb całkowitych pooddzielanych spacjami. Pierwszą liczbą jest n (1 ≤ n ≤ 5*10⁶) - liczba segmentów segmentolka. Po tej liczbie występuje n nieujemnych liczb całkowitych, niewiększych niż 10⁶ - oznaczają one liczby nóżek wyrastających z kolejnych segmentów.

Wyjście

Dla każdego zestawu danych wypisz liczbę oznaczającą minimalny możliwy wiek segmentolka wyrażony w dniach.

Przykład

Wejście:

3
1 0
1 5
4 0 0 0 0

Wyjście:

0
5
2