Ci sono $n$ risonatori disposti in ordine lungo un corridoio. Lo scostamento di frequenza attuale dell'$i$-esimo risonatore è $a_i$, e il suo scostamento obiettivo è $b_i$.

Il dispositivo di sintonizzazione può essere attivato solo da una delle estremità del corridoio. In un'operazione, puoi scegliere un qualsiasi intero non nullo $x$ ed eseguire una delle seguenti operazioni:

1. Scegliere $k$ ($1 \le k \le n$) e sommare $x$ a ogni numero nel prefisso $a_1, a_2, \ldots, a_k$;
2. Scegliere $k$ ($1 \le k \le n$) e sommare $x$ a ogni numero nel suffisso $a_k, a_{k+1}, \ldots, a_n$.

$x$ può essere positivo o negativo. Indipendentemente dalla grandezza di $|x|$, la modifica conta esattamente come un'operazione.

Trova il numero minimo di operazioni necessarie per trasformare la sequenza $a$ nella sequenza $b$.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene un intero $n$ ($1 \le n \le 2 \times 10^5$).
• La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• La terza riga contiene $n$ interi $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

Si garantisce che la somma di $n$ su tutti i casi di test non supera $2 \times 10^5$, e che le somme di $\sum |a_i - a_{i-1}|$ ($i \ge 2$) e $\sum |b_i - b_{i-1}|$ ($i \ge 2$), calcolate su tutti i casi di test, non superano rispettivamente $10^4$.

Output

Per ciascun caso di test, stampa un intero su una riga separata, il numero minimo di operazioni.

Esempi

Input 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

Output 1

2
3
1
0

Note

Per il primo caso di test, una possibile sequenza di operazioni è:

1. Sommare $-3$ a un prefisso di lunghezza $1$, ottenendo $[-3, 0, 0]$.
2. Sommare $2$ a un prefisso di lunghezza $2$, ottenendo $[-1, 2, 0]$.

Per il terzo caso di test, è sufficiente sommare $5$ all'intera sequenza.