Pelaat ruudukon täyttöpeliä. Pelin käyttöliittymässä on useita ruutuja yhdessä rivissä, ja sinun tulee täyttää jokaiseen ruutuun positiivinen kokonaisluku. Järjestelmä laskee sen jälkeen pisteet täyttämiesi lukujen perusteella.

Ennen jokaisen pelikierroksen alkua järjestelmä antaa sinulle rajoitteet ruutujen täyttämiseen. Oletetaan, että nykyisessä pelissä on $n$ ruutua rivissä; järjestelmä antaa kaksi positiivista kokonaislukua $l_i, r_i$ ruudulle $i$ osoittaen, että ruutuun $i$ täyttämäsi luvun $x_i$ on toteutettava ehto $l_i \le x_i \le r_i$. Kun olet täyttänyt luvut, järjestelmä jakaa ruutujonon useisiin osiin erottamalla vierekkäiset ruudut, joissa on eri luku. Tämän jälkeen järjestelmä laskee kunkin osan pituuden neliöiden summan, jota kutsutaan täyttötavan jatkuvuudeksi.

Esimerkiksi täyttötavalle $x = [1, 1, 3, 3, 5, 5, 5, 3, 3]$ osiin jakamisen tulos on $\underline{1, 1}, \underline{3, 3}, \underline{5, 5, 5}, \underline{3, 3}$, ja jatkuvuus vastaa arvoa $2^2 + 2^2 + 3^2 + 2^2 = 21$.

Tämän pelin tavoitteena on minimoida jatkuvuus. Sinun tulee määrittää jatkuvuuden pienin mahdollinen arvo optimaalisella täyttöstrategialla.

Syöte

Sinun tulee vastata usealle pelikierrokselle. Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmoittaa pelikierrosten lukumäärän.

Jokaiselle pelikierrokselle:

Syötteen ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$ ($1 \le n \le 10^6$), joka ilmoittaa ruutujen lukumäärän.

Seuraava rivi sisältää $n$ positiivista kokonaislukua $l_i$ ($1 \le l_i \le 10^9$), jotka kuvaavat kunkin ruudun alarajarajoitteita.

Sitä seuraava rivi sisältää $n$ positiivista kokonaislukua $r_i$ ($1 \le r_i \le 10^9, l_i \le r_i$), jotka kuvaavat kunkin ruudun ylärajarajoitteita.

On taattu, että lukujen $n$ kokonaissumma yli kaikkien pelien ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle pelikierrokselle yksi kokonaisluku, joka ilmaisee jatkuvuuden pienimmän arvon.

Esimerkki

Esimerkkisyöte 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

Esimerkkituloste 1

3
6
17

Huomautus

Pelin ensimmäisellä kierroksella yksi mahdollinen täyttötapa on $x = [3, 1, 4]$, joka vastaa jatkuvuutta $1^2 + 1^2 + 1^2 = 3$.

Pelin toisella kierroksella yksi mahdollinen täyttötapa on $x = [1, 2, 3, 4, 5, 6]$, joka vastaa jatkuvuutta $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$.

Pelin kolmannella kierroksella yksi mahdollinen täyttötapa on $x = [1, 1, 2, 2, 2, 1, 1]$, joka vastaa jatkuvuutta $2^2 + 3^2 + 2^2 = 17$.