VegiCat กำลังปฏิบัติภารกิจเก็บกู้ทุ่นระเบิด มีทุ่นระเบิด $n$ ลูกอยู่บนเส้นจำนวน ทุ่นระเบิดลูกที่ $i$ อยู่ที่พิกัดจำนวนเต็ม $a_i$ ทุ่นระเบิดถูกเรียงลำดับหมายเลขตามพิกัดของมัน ดังนั้น $a_1 \le a_2 \le \cdots \le a_n$ พิกัดของทุ่นระเบิดอาจซ้ำกันได้

VegiCat ทดสอบทุ่นระเบิดแต่ละลูกเพียงครั้งเดียว ตามลำดับ $1, 2, \ldots, n$ สำหรับทุ่นระเบิดลูกที่ $i$ เขาเลือกพิกัดจำนวนเต็ม $b_i$ เป็นตำแหน่งทดสอบ ซึ่งอาจเป็นจำนวนลบหรือศูนย์ก็ได้ ความคลาดเคลื่อนของการทดสอบนี้คือ $|a_i - b_i|$

สำหรับแต่ละ $2 \le i \le n$ จะมีจำนวนเต็ม $l_i$ กำหนดให้ ซึ่งระบุระยะห่างขั้นต่ำที่ต้องการระหว่างตำแหน่งทดสอบของทุ่นระเบิดลูกที่ $i - 1$ และ $i$ ตำแหน่งเหล่านี้ต้องสอดคล้องกับเงื่อนไข

$$|b_i - b_{i-1}| \ge l_i.$$

จงช่วย VegiCat หาค่าต่ำสุดของความคลาดเคลื่อนในการทดสอบที่มากที่สุด กล่าวคือ จงหาค่าของ

$$\min_{\substack{b_1, \ldots, b_n \in \mathbb{Z} \\ |b_i - b_{i-1}| \ge l_i \ (2 \le i \le n)}} \left(\max_{1 \le i \le n} |a_i - b_i|\right).$$

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 10^4$) ซึ่งแทนจำนวนกรณีทดสอบ รายละเอียดของแต่ละกรณีทดสอบมีดังต่อไปนี้

บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็ม $n$ ($2 \le n \le 10^5$) ซึ่งแทนจำนวนทุ่นระเบิด

บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน ได้แก่ $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) โดยที่ $a_i$ คือพิกัดของทุ่นระเบิดลูกที่ $i$ รับประกันว่า $a_1 \le a_2 \le \cdots \le a_n$

บรรทัดที่สามประกอบด้วยจำนวนเต็ม $n - 1$ จำนวน ได้แก่ $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$) โดยที่ $l_i$ คือระยะห่างขั้นต่ำระหว่างตำแหน่งทดสอบของทุ่นระเบิดลูกที่ $i - 1$ และ $i$

รับประกันว่าผลรวมของ $n$ จากทุกกรณีทดสอบจะไม่เกิน $10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลเป็นจำนวนเต็มหนึ่งจำนวน นั่นคือค่าที่น้อยที่สุดที่เป็นไปได้ของความคลาดเคลื่อนในการทดสอบที่มากที่สุด

ตัวอย่าง

ข้อมูลนำเข้า 1

2
2
1 1
1
7
2 6 12 14 14 16 19
11 8 4 2 10 9

ข้อมูลส่งออก 1

1
6

หมายเหตุ

ในกรณีทดสอบแรก การเลือก $b_1 = 1$ และ $b_2 = 2$ จะให้ค่าความคลาดเคลื่อนสูงสุดเท่ากับ $1$ หากต้องการให้ความคลาดเคลื่อนเป็น $0$ จะต้องเลือก $b_1 = b_2 = 1$ ซึ่งผิดเงื่อนไขเรื่องระยะห่าง

ในกรณีทดสอบที่สอง ทางเลือกที่เหมาะสมที่สุดแบบหนึ่งคือ $b = [-4, 7, 15, 10, 8, 22, 13]$ ระยะห่างที่ต้องการทั้งหมดเป็นไปตามเงื่อนไข และความคลาดเคลื่อนสูงสุดคือ $6$