Du spiller et rutefyllingsspill. På spillgrensesnittet er flere ruter stilt opp på én rad, og du må fylle hver rute med et positivt heltall. Systemet vil deretter beregne poengsummen basert på tallene du fyller inn.

Før hver runde av spillet starter, vil systemet gi deg begrensninger for utfyllingen av rutene. Anta at det er $n$ ruter på rad i det gjeldende spillet; systemet vil da oppgi to positive heltall $l_i, r_i$ for den $i$-te ruten, som angir at tallet $x_i$ du fyller inn i den $i$-te ruten må oppfylle $l_i \le x_i \le r_i$. Etter at du har fylt inn tallene, vil systemet dele opp følgen av ruter i flere segmenter basert på naboruter med ulike tall. Systemet vil så beregne summen av kvadratene av lengdene til hvert segment, noe som kalles utfyllingsmåten sin kontinuitet.

For eksempel, for utfyllingsmåten $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ er segmenteringsresultatet $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, og kontinuiteten tilsvarer $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Målet med dette spillet er å minimere kontinuiteten. Du må finne den minste mulige verdien av kontinuiteten under en optimal utfyllingsstrategi.

Inndata

Du må svare for flere runder av spillet. Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), som representerer antallet spillrunder.

For hver runde av spillet:

Den første linjen i inndataene inneholder et positivt heltall $n$ ($1 \le n \le 10^6$), som representerer antallet ruter.

Den neste linjen inneholder $n$ positive heltall $l_i$ ($1 \le l_i \le 10^9$), som representerer nedre grenser for hver rute.

Den påfølgende linjen inneholder $n$ positive heltall $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), som representerer øvre grenser for hver rute.

Det er garantert at den totale summen av $n$ over alle spill ikke overstiger $10^6$.

Utdata

For hver runde av spillet skal du skrive ut et enkelt heltall som representerer minimumsverdien av kontinuiteten.

Eksempel

Eksempelinndata 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

Eksempelutdata 1

3
6
17

Merk

For den første runden av spillet er én mulig utfyllingsmåte $x = [3, 1, 4]$, som tilsvarer en kontinuitet på $1^2 + 1^2 + 1^2 = 3$.

For den andre runden av spillet er én mulig utfyllingsmåte $x = [1, 2, 3, 4, 5, 6]$, som tilsvarer en kontinuitet på $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

For den tredje runden av spillet er én mulig utfyllingsmåte $x = [1, 1, 2, 2, 2, 1, 1]$, som tilsvarer en kontinuitet på $2^2 + 3^2 + 2^2 = 17$.