Du spielst ein Felder-Ausfüllspiel. Auf der Spieloberfläche sind mehrere Felder in einer Reihe angeordnet, und du musst in jedes Feld eine positive ganze Zahl eintragen. Das System berechnet anschließend die Punktzahl basierend auf den von dir eingetragenen Zahlen.

Vor Beginn jeder Spielrunde gibt dir das System Bedingungen für das Ausfüllen der Felder vor. Angenommen, für das aktuelle Spiel sind $n$ Felder in einer Reihe angeordnet, dann gibt das System zwei positive ganze Zahlen $l_i, r_i$ für das $i$-te Feld vor, was bedeutet, dass die Zahl $x_i$, die du in das $i$-te Feld einträgst, $l_i \le x_i \le r_i$ erfüllen muss. Nachdem du die Zahlen eingetragen hast, unterteilt das System die Folge von Feldern anhand benachbarter Felder mit unterschiedlichen Zahlen in mehrere Abschnitte. Anschließend berechnet das System die Summe der Quadrate der Längen jedes Abschnitts, was als Kontinuität des Ausfüllschemas bezeichnet wird.

Für das Ausfüllschema $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ lautet das Ergebnis der Unterteilung beispielsweise $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, und die Kontinuität entspricht $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Das Ziel dieses Spiels ist es, die Kontinuität zu minimieren. Du musst den minimalen Wert der Kontinuität unter der optimalen Ausfüllstrategie bestimmen.

Eingabe

Du musst für mehrere Spielrunden antworten. Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Spielrunden angibt.

Für jede Spielrunde:

Die erste Zeile der Eingabe enthält eine positive ganze Zahl $n$ ($1 \le n \le 10^6$), die die Anzahl der Felder angibt.

Die nächste Zeile enthält $n$ positive ganze Zahlen $l_i$ ($1 \le l_i \le 10^9$), die die unteren Schranken für jedes Feld darstellen.

Die darauffolgende Zeile enthält $n$ positive ganze Zahlen $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), die die oberen Schranken für jedes Feld darstellen.

Es ist garantiert, dass die Gesamtsumme von $n$ über alle Spiele hinweg $10^6$ nicht überschreitet.

Ausgabe

Gib für jede Spielrunde eine einzelne ganze Zahl aus, die den minimalen Wert der Kontinuität darstellt.

Beispiel

Beispieleingabe 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

Beispielausgabe 1

3
6
17

Hinweis

Für die erste Spielrunde ist ein mögliches Ausfüllschema $x = [3, 1, 4]$, was einer Kontinuität von $1^2 + 1^2 + 1^2 = 3$ entspricht.

Für die zweite Spielrunde ist ein mögliches Ausfüllschema $x = [1, 2, 3, 4, 5, 6]$, was einer Kontinuität von $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$ entspricht.

Für die dritte Spielrunde ist ein mögliches Ausfüllschema $x = [1, 1, 2, 2, 2, 1, 1]$, was einer Kontinuität von $2^2 + 3^2 + 2^2 = 17$ entspricht.