Käytävän varrelle on asetettu järjestyksessä $n$ resonaattoria. $i$-nnen resonaattorin nykyinen taajuuspoikkeama on $a_i$ ja sen tavoitepoikkeama on $b_i$.

Virityslaite voidaan aktivoida vain käytävän toisesta päästä. Yhdessä operaatiossa voit valita minkä tahansa nollasta poikkeavan kokonaisluvun $x$ ja suorittaa toisen seuraavista operaatioista:

1. Valitse $k$ ($1 \le k \le n$) ja lisää $x$ jokaiseen lukuun alkuosassa $a_1, a_2, \ldots, a_k$;
2. Valitse $k$ ($1 \le k \le n$) ja lisää $x$ jokaiseen lukuun loppuosassa $a_k, a_{k+1}, \ldots, a_n$.

$x$ voi olla positiivinen tai negatiivinen. Riippumatta luvun $|x|$ suuruudesta muutos lasketaan täsmälleen yhdeksi operaatioksi.

Etsi pienin määrä operaatioita, jotka tarvitaan lukujonon $a$ muuttamiseksi lukujonoksi $b$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), testitapausten lukumäärän.

Jokaisessa testitapauksessa:

• Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \times 10^5$).
• Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• Kolmas rivi sisältää $n$ kokonaislukua $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \times 10^5$, ja että summien $\sum |a_i - a_{i-1}|$ ($i \ge 2$) sekä $\sum |b_i - b_{i-1}|$ ($i \ge 2$) summat yli kaikkien testitapausten eivät kumpikaan ylitä arvoa $10^4$.

Tuloste

Tulosta jokaista testitapausta kohden omalle rivilleen yksi kokonaisluku, pienin tarvittava operaatioiden määrä.

Esimerkit

Syöte 1

4
3
0 0 0
-1 2 0
3
0 0 0
3 1 4
4
1 4 2 8
6 9 7 13
2
-7 10
-7 10

Tuloste 1

2
3
1
0

Huomautus

Ensimmäisessä testitapauksessa eräs mahdollinen operaatioiden sarja on:

1. Lisätään $-3$ pituuden $1$ alkuosaan, jolloin saadaan $[-3, 0, 0]$.
2. Lisätään $2$ pituuden $2$ alkuosaan, jolloin saadaan $[-1, 2, 0]$.

Kolmannessa testitapauksessa riittää lisätä $5$ koko lukujonoon.