אתם משחקים במשחק מילוי משבצות. בממשק המשחק מסודרות מספר משבצות בשורה, ועליכם למלא כל משבצת במספר שלם חיובי. לאחר מכן המערכת תחשב את הניקוד בהתבסס על המספרים שמילאתם.

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