Grasz w grę polegającą na wypełnianiu pól. W interfejsie gry w jednym rzędzie ułożonych jest kilka pól, a w każde z nich musisz wpisać dodatnią liczbę całkowitą. Następnie system obliczy wynik na podstawie wpisanych przez Ciebie liczb.

Przed rozpoczęciem każdej rundy gry system przekaże Ci ograniczenia dotyczące wypełniania pól. Załóżmy, że w bieżącej grze w rzędzie znajduje się $n$ pól; wówczas dla $i$-tego pola system poda dwie dodatnie liczby całkowite $l_i, r_i$, oznaczające, że liczba $x_i$ wpisana w $i$-te pole musi spełniać warunek $l_i \le x_i \le r_i$. Po wpisaniu wszystkich liczb system podzieli ciąg pól na kilka przedziałów, rozdzielając sąsiednie pola zawierające różne liczby. Następnie system obliczy sumę kwadratów długości każdego przedziału, nazywaną ciągłością sposobu wypełnienia.

Na przykład dla sposobu wypełnienia $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ wynikiem podziału na przedziały jest $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, a ciągłość wynosi $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Celem tej gry jest zminimalizowanie ciągłości. Musisz wyznaczyć minimalną wartość ciągłości przy optymalnej strategii wypełniania pól.

Wejście

Musisz udzielić odpowiedzi dla wielu rund gry. Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę rund gry.

Dla każdej rundy gry:

Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą $n$ ($1 \le n \le 10^6$), oznaczającą liczbę pól.

Następny wiersz zawiera $n$ dodatnich liczb całkowitych $l_i$ ($1 \le l_i \le 10^9$), oznaczających dolne ograniczenia dla poszczególnych pól.

Kolejny wiersz zawiera $n$ dodatnich liczb całkowitych $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), oznaczających górne ograniczenia dla poszczególnych pól.

Gwarantowane jest, że łączna suma $n$ we wszystkich grach nie przekracza $10^6$.

Wyjście

Dla każdej rundy gry wypisz pojedynczą liczbę całkowitą oznaczającą minimalną wartość ciągłości.

Przykład

Przykładowe wejście 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

Przykładowe wyjście 1

3
6
17

Uwaga

W pierwszej rundzie gry jednym z możliwych sposobów wypełnienia jest $x = [3, 1, 4]$, co odpowiada ciągłości równej $1^2 + 1^2 + 1^2 = 3$.

W drugiej rundzie gry jednym z możliwych sposobów wypełnienia jest $x = [1, 2, 3, 4, 5, 6]$, co odpowiada ciągłości równej $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

W trzeciej rundzie gry jednym z możliwych sposobów wypełnienia jest $x = [1, 1, 2, 2, 2, 1, 1]$, co odpowiada ciągłości równej $2^2 + 3^2 + 2^2 = 17$.