Problem Description

Along a corridor, $n$ resonators are placed in order. The current frequency offset of the $i$-th resonator is $a_i$, and the 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 non-zero integer $x$, and perform one of the following two actions:

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

$x$ can be positive or negative. No matter how large $|x|$ is, this modification counts as exactly one operation.

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

Input Format

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$. Also, over all test cases, the sum of $\sum |a_i-a_{i-1}|(i\ge 2)$ and the sum of $\sum |b_i-b_{i-1}|(i\ge 2)$ are each no more than $10^4$.

Output Format

For each test case, output one line with one integer, the minimum number of operations.

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

2
3
1
0

Hint

For the first test case, you can do:

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

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

Translated by ChatGPT 5