לאחר שפתר את בעיית סכום תת-הקבוצה (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$.