你而家玩緊一個填格仔遊戲。喺遊戲介面上面，有若干個方格排成一排，你需要喺每個方格入面填入一個正整數。之後系統會根據你填入嘅數字嚟計分。

喺每一輪遊戲開始之前，系統會向你提供填方格嘅限制條件。假設當前呢輪遊戲有 $n$ 個方格排成一排，系統會為第 $i$ 個方格提供兩個正整數 $l_i, r_i$，代表你喺第 $i$ 個方格入面填入嘅數字 $x_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$。