시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

Hektor ze Zbyszkiem codziennie rano wybierają się po ciastka. Ciastkarz przygotowuje każdorazowo N ciastek, z których każde opisuje jedna liczba naturalna reprezentująca jego jakość. Chłopcy na zmianę wybierają po jednym ciastku, zawsze wybierając najlepsze z dostępnych jeszcze ciastek.

W tym tygodniu na Zbyszka przypada kolej dokonywania pierwszego wyboru, co jest zdaniem Hektora bardzo niesprawiedliwe. Hektor chciałby, żeby przewaga Zbyszka (suma jakości ciastek wybranych przez Zbyszka pomniejszona o sumę jakości ciastek Hektora) była możliwie mała. Aby osiągnąć ten cel postanowił uciec się do drobnej manipulacji. 

Hektor zadzwonił wcześnie rano do kończącego pracę ciastkarza i zapytał o ciastka przygotowane na dzisiaj. Ciastkarz bardzo lubi Hektora i może na jego prośbę uzupełnić ten zbiór o jeszcze jedno jedno ciastko wybranej przez Hektora jakości.

Znając jakości przygotowanych ciastek i mogąc uzupełnić ten zbiór o maksymalnie jedno ciastko dowolnej ( naturalnej ) jakości oblicz minimalną osiągalną przewagę Zbyszka nad Hektorem.

입력

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z<= 10 ). Następniepodawane są kolejne zestawy testowe.

Każdy zestaw zaczyna się od liczby naturalnej N ( 1 <= N <= 1000000 ) oznaczającej liczbę ciastek przygotowanych przez ciastkarza.

W drugiej linii zestawu znajduje się N liczb naturalnych Areprezentujących jakości kolejnych ciastek ( 1 <= Ai <= 1000 ).

출력

Dla każdego przypadku testowego wypisz w osobnej linii minimalną różnicę pomiędzy jakością ciastek Zbyszka a jakością ciastek Hektora.

예제 입력 1

4 
2 
1 1 
2 
1 2 
3 
1 1 1 
5 
16 15 7 8 3

예제 출력 1

0
1
0
2