당신은 격자 채우기 게임을 플레이하고 있습니다. 게임 화면에는 여러 개의 칸이 한 줄로 나열되어 있으며, 각 칸에 양의 정수를 하나씩 채워 넣어야 합니다. 그러면 시스템은 당신이 채워 넣은 숫자들을 바탕으로 점수를 계산합니다.

게임의 각 라운드가 시작되기 전에, 시스템은 칸을 채우는 데 필요한 제약 조건을 제공합니다. 현재 게임에 $n$개의 칸이 한 줄로 나열되어 있다고 할 때, 시스템은 $i$번째 칸에 대해 두 양의 정수 $l_i, r_i$를 제공하며, 이는 $i$번째 칸에 채워 넣는 수 $x_i$가 반드시 $l_i \le x_i \le r_i$를 만족해야 함을 의미합니다. 숫자들을 모두 채워 넣은 후, 시스템은 서로 다른 숫자가 적힌 인접한 칸들을 기준으로 칸들의 수열을 여러 구간으로 나눕니다. 그런 다음 시스템은 각 구간의 길이의 제곱의 합을 계산하며, 이를 해당 채우기 방법의 연속도(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

참고

첫 번째 라운드의 경우, 가능한 채우기 방법 중 하나는 $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$입니다.