أنت تلعب لعبة ملء المربعات. على واجهة اللعبة، توجد عدة مربعات مرتبة في صف واحد، وعليك ملء كل مربع بعدد صحيح موجب. سيقوم النظام بعد ذلك بحساب النتيجة بناءً على الأعداد التي أدخلتها.

قبل بدء كل جولة من اللعبة، سيزودك النظام بقيود لملء المربعات. لنفترض أن هناك $n$ من المربعات مرتبة في صف واحد للعبة الحالية؛ سيوفر النظام عددين صحيحين موجبين $l_i, r_i$ للمربع ذي الترتيب $i$، مما يشير إلى أن العدد $x_i$ الذي تضعه في المربع ذي الترتيب $i$ يجب أن يحقق $l_i \le x_i \le r_i$. بعد أن تقوم بملء الأعداد، سيفصل النظام متتالية المربعات إلى عدة مقاطع بناءً على المربعات المتجاورة التي تحتوي على أعداد مختلفة. ثم يحسب النظام مجموع مربعات أطوال كل مقطع، وهو ما يُشار إليه باسم استمرارية مخطط الملء.

على سبيل المثال، بالنسبة لمخطط الملء $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$.