Il y a $n$ résonateurs placés dans l'ordre le long d'un couloir. Le décalage de fréquence actuel du $i$-ème résonateur est $a_i$, et son décalage cible est $b_i$.

Le dispositif d'accordage ne peut être activé que depuis l'une des extrémités du couloir. En une opération, vous pouvez choisir n'importe quel entier non nul $x$ et effectuer l'une des opérations suivantes :

1. Choisir $k$ ($1 \le k \le n$) et ajouter $x$ à chaque nombre du préfixe $a_1, a_2, \ldots, a_k$ ;
2. Choisir $k$ ($1 \le k \le n$) et ajouter $x$ à chaque nombre du suffixe $a_k, a_{k+1}, \ldots, a_n$.

$x$ peut être positif ou négatif. Quelle que soit la grandeur de $|x|$, la modification compte pour exactement une opération.

Trouvez le nombre minimum d'opérations nécessaires pour transformer la suite $a$ en la suite $b$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient un entier $n$ ($1 \le n \le 2 \times 10^5$).
• La deuxième ligne contient $n$ entiers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• La troisième ligne contient $n$ entiers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \times 10^5$, et que les sommes de $\sum |a_i - a_{i-1}|$ ($i \ge 2$) et de $\sum |b_i - b_{i-1}|$ ($i \ge 2$), prises sur tous les cas de test, ne dépassent pas $10^4$ respectivement.

Sortie

Pour chaque cas de test, affichez un entier sur une ligne séparée, représentant le nombre minimum d'opérations.

Exemples

Entrée 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

Sortie 1

2
3
1
0

Remarque

Pour le premier cas de test, une suite possible d'opérations est :

1. Ajouter $-3$ à un préfixe de longueur $1$, ce qui donne $[-3, 0, 0]$.
2. Ajouter $2$ à un préfixe de longueur $2$, ce qui donne $[-1, 2, 0]$.

Pour le troisième cas de test, il suffit d'ajouter $5$ à toute la suite.