หลังจากแก้ปัญหาผลรวมของเซตย่อย (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$