Það eru $n$ ómarar settir í röð eftir gangi. Núverandi tíðnihliðrun $i$-ta ómarans er $a_i$ og markhliðrun hans er $b_i$.

Stillingartækið er aðeins hægt að virkja frá öðrum enda gangsins. Í einni aðgerð máttu velja hvaða heiltölu $x$ sem er, frábrugðna núlli, og framkvæma annaðhvort af eftirfarandi:

1. Velja $k$ ($1 \le k \le n$) og leggja $x$ við hverja tölu í forkeytinu $a_1, a_2, \ldots, a_k$;
2. Velja $k$ ($1 \le k \le n$) og leggja $x$ við hverja tölu í viðkeytinu $a_k, a_{k+1}, \ldots, a_n$.

$x$ getur verið jákvæð eða neikvæð. Óháð stærð $|x|$ telst breytingin sem nákvæmlega ein aðgerð.

Finndu lágmarksfjölda aðgerða sem þarf til að breyta rununni $a$ í rununa $b$.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \times 10^5$).
• Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• Þriðja línan inniheldur $n$ heiltölur $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \times 10^5$, og að summur $\sum |a_i - a_{i-1}|$ ($i \ge 2$) og $\sum |b_i - b_{i-1}|$ ($i \ge 2$) yfir öll prófunartilvik fari hvor um sig ekki yfir $10^4$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu á sérstaka línu, lágmarksfjölda aðgerða.

Dæmi

Inntak 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

Úttak 1

2
3
1
0

Athugasemd

Fyrir fyrsta prófunartilvikið er ein möguleg röð aðgerða:

1. Leggja $-3$ við forkeyti af lengd $1$, sem gefur $[-3, 0, 0]$.
2. Leggja $2$ við forkeyti af lengd $2$, sem gefur $[-1, 2, 0]$.

Fyrir þriðja prófunartilvikið nægir að leggja $5$ við alla rununa.