Þú ert að spila reitafyllingarleik. Á leikjaviðmótinu er nokkrum reitum raðað í röð og þú þarft að fylla hvern reit með jákvæðri heiltölu. Kerfið mun síðan reikna út stigin út frá tölunum sem þú fyllir inn.

Áður en hver umferð leiksins hefst mun kerfið láta þig fá skorður fyrir útfyllingu reitanna. Gerum ráð fyrir að $n$ reitum sé raðað í röð í núverandi leik; kerfið mun þá gefa tvær jákvæðar heiltölur $l_i, r_i$ fyrir $i$-ta reitinn, sem gefa til kynna að talan $x_i$ sem þú fyllir í $i$-ta reitinn verði að uppfylla $l_i \le x_i \le r_i$. Eftir að þú hefur fyllt inn tölurnar mun kerfið skipta runu reitanna í nokkra búta út frá aðliggjandi reitum með ólíkum tölum. Kerfið mun síðan reikna summu ferninga lengda hvers búts, sem kallast samfellni útfyllingarinnar.

Til dæmis, fyrir útfyllinguna $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ er niðurstaða bútaskiptingarinnar $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$ og samfellnin samsvarar $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Markmið þessa leiks er að lágmarka samfellni. Þú þarft að ákvarða lágmarksgildi samfellni við bestu mögulegu útfyllingaráætlun.

Inntak

Þú þarft að svara fyrir margar umferðir leiksins. Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), sem táknar fjölda leikjaumferða.

Fyrir hverja umferð leiksins:

Fyrsta lína inntaksins inniheldur jákvæða heiltölu $n$ ($1 \le n \le 10^6$), sem táknar fjölda reita.

Næsta lína inniheldur $n$ jákvæðar heiltölur $l_i$ ($1 \le l_i \le 10^9$), sem tákna neðri mörk fyrir hvern reit.

Línan þar á eftir inniheldur $n$ jákvæðar heiltölur $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), sem tákna efri mörk fyrir hvern reit.

Tryggt er að heildarsumma $n$ yfir alla leiki fari ekki yfir $10^6$.

Úttak

Fyrir hverja umferð leiksins skal prenta eina heiltölu sem táknar lágmarksgildi samfellni.

Dæmi

Sýnidæmi inntaks 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

Sýnidæmi úttaks 1

3
6
17

Athugasemd

Fyrir fyrstu umferð leiksins er ein möguleg útfylling $x = [3, 1, 4]$, sem samsvarar samfellni upp á $1^2 + 1^2 + 1^2 = 3$.

Fyrir aðra umferð leiksins er ein möguleg útfylling $x = [1, 2, 3, 4, 5, 6]$, sem samsvarar samfellni upp á $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

Fyrir þriðju umferð leiksins er ein möguleg útfylling $x = [1, 1, 2, 2, 2, 1, 1]$, sem samsvarar samfellni upp á $2^2 + 3^2 + 2^2 = 17$.