あなたはマス埋めゲームをプレイしています。ゲーム画面にはいくつかのマスが横一列に並んでおり、各マスに正の整数を1つずつ書き込む必要があります。その後、書き込んだ数値に基づいてシステムがスコアを計算します。

ゲームの各ラウンドが始まる前に、システムからマスを埋める際の制約が与えられます。現在のゲームで $n$ 個のマスが一列に並んでいるとすると、システムは $i$ 番目のマスに対して2つの正の整数 $l_i, r_i$ を与え、$i$ 番目のマスに書き込む数 $x_i$ が $l_i \le x_i \le r_i$ を満たさなければならないことを示します。すべてのマスに数を書き終えると、システムは隣り合うマスの数が異なる箇所でマスの列をいくつかの区間に分割します。そして各区間の長さの2乗の総和を計算します。この値をその書き込み方の連続度（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

注記

第1ラウンドでは、可能な書き込み方の1つとして $x = [3, 1, 4]$ があり、これに対応する連続度は $1^2 + 1^2 + 1^2 = 3$ です。

第2ラウンドでは、可能な書き込み方の1つとして $x = [1, 2, 3, 4, 5, 6]$ があり、これに対応する連続度は $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$ です。

第3ラウンドでは、可能な書き込み方の1つとして $x = [1, 1, 2, 2, 2, 1, 1]$ があり、これに対応する連続度は $2^2 + 3^2 + 2^2 = 17$ です。