RCPC Simulare 2023 day 2 | A. Maximum Distance

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$.

Task

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$.

Examples

stdin

7
6
-1 -4 2 -5 -2 10
4 4 -8 2 -4 -8
4
6 2 3 4
2 6 7 4
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
1 2 3 4
5 6 7 4
4
1 2 3 4
1 2 3 5

stdout

6
3
5
5
5
3
3