Du spelar ett rutfyllnadsspel. I spelgränssnittet är flera rutor placerade i en rad, och du ska fylla varje ruta med ett positivt heltal. Systemet beräknar sedan poängen baserat på de tal du fyller i.

Innan varje spelrunda börjar ger systemet dig begränsningar för hur rutorna får fyllas i. Antag att det finns $n$ rutor i en rad i det aktuella spelet; systemet ger då två positiva heltal $l_i, r_i$ för den $i$-te rutan, vilket anger att talet $x_i$ som du fyller i den $i$-te rutan måste uppfylla $l_i \le x_i \le r_i$. När du har fyllt i talen delar systemet upp följden av rutor i flera segment baserat på intilliggande rutor med olika tal. Systemet beräknar därefter summan av kvadraterna på längderna av varje segment, vilket kallas fyllningsschemats kontinuitet.

Till exempel, för fyllningsschemat $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ blir segmenteringsresultatet $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, och kontinuiteten motsvarar $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Målet med detta spel är att minimera kontinuiteten. Du ska bestämma det minsta möjliga värdet på kontinuiteten under en optimal fyllningsstrategi.

Indata

Du ska svara för flera rundor av spelet. Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^5$), som representerar antalet spelrundor.

För varje spelrunda:

Den första raden i indatan innehåller ett positivt heltal $n$ ($1 \le n \le 10^6$), som representerar antalet rutor.

Nästa rad innehåller $n$ positiva heltal $l_i$ ($1 \le l_i \le 10^9$), som representerar de undre gränserna för varje ruta.

Följande rad innehåller $n$ positiva heltal $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), som representerar de övre gränserna för varje ruta.

Det garanteras att den totala summan av $n$ över alla spel inte överstiger $10^6$.

Utdata

För varje spelrunda, skriv ut ett enda heltal som representerar det minsta värdet på kontinuiteten.

Exempel

Exempelindata 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

Exempelutdata 1

3
6
17

Notera

För den första spelrundan är ett möjligt fyllningsschema $x = [3, 1, 4]$, vilket motsvarar en kontinuitet på $1^2 + 1^2 + 1^2 = 3$.

För den andra spelrundan är ett möjligt fyllningsschema $x = [1, 2, 3, 4, 5, 6]$, vilket motsvarar en kontinuitet på $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

För den tredje spelrundan är ett möjligt fyllningsschema $x = [1, 1, 2, 2, 2, 1, 1]$, vilket motsvarar en kontinuitet på $2^2 + 3^2 + 2^2 = 17$.