بعد حل مسألة مجموع المجموعة الجزئية في زمن $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$.