Вдоль коридора по порядку расположены $n$ резонаторов. Текущее смещение частоты $i$-го резонатора равно $a_i$, а его целевое смещение равно $b_i$.

Настроечное устройство можно активировать только с одного из концов коридора. За одну операцию вы можете выбрать любое ненулевое целое число $x$ и выполнить одно из следующих действий:

1. Выбрать $k$ ($1 \le k \le n$) и прибавить $x$ к каждому числу в префиксе $a_1, a_2, \ldots, a_k$;
2. Выбрать $k$ ($1 \le k \le n$) и прибавить $x$ к каждому числу в суффиксе $a_k, a_{k+1}, \ldots, a_n$.

Число $x$ может быть как положительным, так и отрицательным. Независимо от величины $|x|$, такое изменение считается ровно за одну операцию.

Найдите минимальное количество операций, необходимое для преобразования последовательности $a$ в последовательность $b$.

Входные данные

Первая строка содержит целое число $T$ ($1 \le T \le 10^4$) — количество наборов входных данных.

Для каждого набора входных данных:

• Первая строка содержит целое число $n$ ($1 \le n \le 2 \times 10^5$).
• Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• Третья строка содержит $n$ целых чисел $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \times 10^5$, а суммы $\sum |a_i - a_{i-1}|$ ($i \ge 2$) и $\sum |b_i - b_{i-1}|$ ($i \ge 2$) по всем наборам входных данных не превосходят $10^4$ соответственно.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — минимальное количество операций.

Примеры

Входные данные 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

Выходные данные 1

2
3
1
0

Примечание

Для первого набора входных данных одна из возможных последовательностей операций такова:

1. Прибавить $-3$ к префиксу длины $1$, получив $[-3, 0, 0]$.
2. Прибавить $2$ к префиксу длины $2$, получив $[-1, 2, 0]$.

Для третьего набора входных данных достаточно прибавить $5$ ко всей последовательности.