There are $n$ resonators placed in order along a corridor. The current frequency offset of the $i$-th resonator is $a_i$, and its target offset is $b_i$.

The tuning device can only be activated from one end of the corridor. In one operation, you may choose any nonzero integer $x$ and perform one of the following operations:

1. Choose $k$ ($1 \le k \le n$) and add $x$ to every number in the prefix $a_1, a_2, \ldots, a_k$;
2. Choose $k$ ($1 \le k \le n$) and add $x$ to every number in the suffix $a_k, a_{k+1}, \ldots, a_n$.

$x$ may be positive or negative. Regardless of the magnitude of $|x|$, the modification counts as exactly one operation.

Find the minimum number of operations required to transform sequence $a$ into sequence $b$.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases.

For each test case:

• The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$).
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).
• The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($-10^9 \le b_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$, and the sums of $\sum |a_i - a_{i-1}|$ ($i \ge 2$) and $\sum |b_i - b_{i-1}|$ ($i \ge 2$), taken over all test cases, do not exceed $10^4$ respectively.

Output

For each test case, output one integer on a separate line, the minimum number of operations.

Examples

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

For the first test case, one possible sequence of operations is:

1. Add $-3$ to a prefix of length $1$, obtaining $[-3, 0, 0]$.
2. Add $2$ to a prefix of length $2$, obtaining $[-1, 2, 0]$.

For the third test case, adding $5$ to the entire sequence is sufficient.