D. Corridor Tuning
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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\le10^4)$$$, the number of test cases.

For each test case:

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

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\times10^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.

Example
Input
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
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.