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

ก่อนที่แต่ละรอบของเกมจะเริ่มขึ้น ระบบจะกำหนดเงื่อนไขสำหรับการเติมตัวเลขในช่อง สมมติว่ามีช่องสี่เหลี่ยม $n$ ช่องเรียงกันเป็นแถวสำหรับเกมในรอบปัจจุบัน ระบบจะกำหนดจำนวนเต็มบวกสองจำนวน $l_i, r_i$ สำหรับช่องที่ $i$ ซึ่งหมายความว่าตัวเลข $x_i$ ที่คุณเติมลงในช่องที่ $i$ จะต้องสอดคล้องกับ $l_i \le x_i \le r_i$ หลังจากที่คุณเติมตัวเลขครบแล้ว ระบบจะแบ่งลำดับของช่องออกเป็นหลายส่วนย่อยโดยแยกตามช่องที่อยู่ติดกันที่มีตัวเลขต่างกัน จากนั้นระบบจะคำนวณผลรวมของกำลังสองของความยาวของแต่ละส่วนย่อย ซึ่งเรียกว่า ความต่อเนื่อง (continuity) ของรูปแบบการเติมตัวเลขนั้น

ตัวอย่างเช่น สำหรับรูปแบบการเติมตัวเลข $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ ผลลัพธ์ของการแบ่งส่วนคือ $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$ และความต่อเนื่องจะตรงกับ $2^2 + 2^2 + 3^2 + 2^2 = 21$

เป้าหมายของเกมนี้คือ ทำให้ความต่อเนื่องมีค่าน้อยที่สุด คุณต้องหาค่าต่ำสุดของความต่อเนื่องภายใต้กลยุทธ์การเติมตัวเลขที่เหมาะสมที่สุด

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

คุณต้องตอบคำถามสำหรับหลายรอบของเกม บรรทัดแรกมีจำนวนเต็ม $T$ ($1 \le T \le 10^5$) แทนจำนวนรอบของเกม

สำหรับแต่ละรอบของเกม:

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มบวก $n$ ($1 \le n \le 10^6$) แทนจำนวนช่องสี่เหลี่ยม

บรรทัดถัดไปมีจำนวนเต็มบวก $n$ จำนวน คือ $l_i$ ($1 \le l_i \le 10^9$) แทนเงื่อนไขขอบเขตล่างของแต่ละช่อง

บรรทัดถัดมามีจำนวนเต็มบวก $n$ จำนวน คือ $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$) แทนเงื่อนไขขอบเขตบนของแต่ละช่อง

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

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

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

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

3
3
1 1 4
5 1 4
6
1 2 3 4 4 4
3 3 3 4 5 6
7
1 1 2 2 1 1 1
1 2 2 2 2 1 1

ข้อมูลส่งออกตัวอย่าง 1

3
6
17

หมายเหตุ

สำหรับรอบแรกของเกม รูปแบบการเติมตัวเลขที่เป็นไปได้แบบหนึ่งคือ $x = [3, 1, 4]$ ซึ่งมีความต่อเนื่องเท่ากับ $1^2 + 1^2 + 1^2 = 3$

สำหรับรอบที่สองของเกม รูปแบบการเติมตัวเลขที่เป็นไปได้แบบหนึ่งคือ $x = [1, 2, 3, 4, 5, 6]$ ซึ่งมีความต่อเนื่องเท่ากับ $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$

สำหรับรอบที่สามของเกม รูปแบบการเติมตัวเลขที่เป็นไปได้แบบหนึ่งคือ $x = [1, 1, 2, 2, 2, 1, 1]$ ซึ่งมีความต่อเนื่องเท่ากับ $2^2 + 3^2 + 2^2 = 17$