Ішкі жиын қосындысы есебін (Subset Sum problem) $O(2^{0.49n})$ уақытта шығарғаннан кейін, Little Cyan Fish сіздің келесі тапсырманы орындағаныңызды қалайды.

Little Cyan Fish-те $n$ карта бар. $i$-ші картада ($1 \le i \le n$) теріс емес $a_i$ бүтін саны жазылған.

Карта индекстерінің әрбір $S \subseteq [n]$ ішкі жиыны үшін, мұндағы $[n] = \{1, 2, \ldots, n\}$, ол таңдалған карталардағы бүтін сандардың қосындысын, яғни $\sum_{i \in S} a_i$ мәнін жазып алады. Бос ішкі жиын үшін қосынды $0$-ге тең. Әртүрлі ішкі жиындар, олардың қосындылары тең болса да, бөлек жазылып алынады.

Барлық $2^n$ ішкі жиынды қарастырып шыққаннан кейін, ол осы $2^n$ қосындыны кемімейтін ретпен сұрыптайды және оларды $s_0, s_1, \ldots, s_{2^n-1}$ деп белгілейді. Little Cyan Fish сізден екі көршілес қосындының арасындағы ең үлкен айырманы табуды сұрайды, яғни:

$$\max_{0 \le i < 2^n - 1} (s_{i+1} - s_i).$$

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін бірінші жолда карталардың санын білдіретін бір бүтін сан $n$ ($1 \le n \le 10^6$) берілген. Екінші жолда карталарда жазылған бүтін сандарды білдіретін $n$ бүтін сан $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $10^6$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін жеке жолға бір бүтін санды — екі көршілес қосындының арасындағы ең үлкен айырманы шығарыңыз.

Мысалдар

Кіріс деректер 1

4
1
0
3
2 3 10
3
1 1 3
3
0 4 4

Шығыс деректер 1

0
5
1
4

Ескертпе

Бірінші мысалдағы тест жағдайында екі ішкі жиын қосындысы да $0$-ге тең, сондықтан жауап $0$.

Екінші мысалдағы тест жағдайында сұрыпталған ішкі жиын қосындылары $0, 2, 3, 5, 10, 12, 13, 15$ болады. Ең үлкен айырма — $5$, ол $5$ пен $10$ арасында.

Үшінші мысалдағы тест жағдайында сұрыпталған ішкі жиын қосындылары $0, 1, 1, 2, 3, 4, 4, 5$ болады. Жауап $1$.

Төртінші мысалдағы тест жағдайында сұрыпталған ішкі жиын қосындылары $0, 0, 4, 4, 4, 4, 8, 8$ болады. Жауап $4$.