A. Maximum Distance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Before giving you the problem statement, we will define $$$dist([x_1, x_2, \dots x_k], [y_1, y_2, \dots y_k])$$$ as the number of indexes $$$i$$$ ($$$1 \leq i \leq k$$$) such that $$$x_i \neq y_i$$$.

You are given $$$n$$$ and two arrays $$$a_1, a_2, \dots a_n$$$ and $$$b_1, b_2, \dots b_n$$$. Find the maximum $$$dist$$$ when choosing any two subarrays of your choice (one from $$$a$$$ and one from $$$b$$$) that have the same length. A subarray of $$$c$$$ is a contiguous part of an array $$$c$$$, i. e. the array $$$c_i, c_{i+1}, \dots c_j$$$ for some $$$1 \leq i \leq j \leq n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) the number of test cases. Then follows the description of the test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10 \ 000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$10 \ 000$$$.

Output

For each test case, print a single integer - the maximum $$$dist$$$ of two subarrays of equal length, one from array $$$a$$$ and the other on from array $$$b$$$.

Example
Input
7
6
-1 -4 2 -5 -2 10
4 4 -8 2 -4 -8
6
4 -7 -3 10 6 5
4 4 4 4 6 4
6
-4 2 -10 -2 -9 10
-4 -4 2 -2 -9 10
6
12 7 -7 -6 -9 -7
-9 12 -7 12 -9 12
4
6 2 3 4
2 6 7 4
4
1 2 3 4
5 6 7 4
4
1 2 3 4
1 2 3 5
Output
6
5
5
5
3
3
3