你正在玩一個填格子遊戲。在遊戲介面上，有若干個方格排成一列，你需要在每個方格中填入一個正整數。系統隨後會根據你填入的數字來計算得分。

在每輪遊戲開始前，系統會為你提供填入方格的限制條件。假設當前遊戲中有 $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$。