你正在玩一个填格子游戏。在游戏界面上，有若干个方格排成一排，你需要往每个方格里填入一个正整数。系统随后会根据你填入的数字来计算得分。

在每轮游戏开始前，系统会为你提供填入方格的限制条件。假设当前游戏中有 $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]$，划分结果为 $[1, 1]$、$[3, 3]$、$[5, 5, 5]$、$[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$。