E. Lost Soul
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integer arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$.

You may perform the following operation any number of times:

  • Choose an index $$$i$$$ $$$(1 \le i \le n - 1)$$$, and set $$$a_i := b_{i + 1}$$$, or set $$$b_i := a_{i + 1}$$$.

Before performing any operations, you are allowed to choose an index $$$i$$$ $$$(1 \le i \le n)$$$ and remove both $$$a_i$$$ and $$$b_i$$$ from the arrays. This removal can be done at most once.

Let the number of matches between two arrays $$$c$$$ and $$$d$$$ of length $$$m$$$ be the number of positions $$$j$$$ $$$(1 \le j \le m)$$$ such that $$$c_j = d_j$$$.

Your task is to compute the maximum number of matches you can achieve.

Input

The first line of the input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of each test case follows.

The first line contains an integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — the length of $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$ — the elements of $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le n)$$$ — the elements of $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the answer for the test case.

Example
Input
10
4
1 3 1 4
4 3 2 2
6
2 1 5 3 6 4
3 2 4 5 1 6
2
1 2
2 1
6
2 5 1 3 6 4
3 5 2 3 4 6
4
1 3 2 2
2 1 3 4
8
3 1 4 6 2 2 5 7
4 2 3 7 1 1 6 5
10
5 1 2 7 3 9 4 10 6 8
6 2 3 6 4 10 5 1 7 9
5
3 2 4 1 5
2 4 5 1 3
7
2 2 6 4 1 3 5
3 1 6 5 1 4 2
5
4 1 3 2 5
3 2 1 5 4
Output
3
3
0
4
3
5
6
4
5
2
Note

In the first test case, we can do the following:

  • We will choose not to remove any index.
  • Choose index $$$3$$$, and set $$$a_3 := b_4$$$. The arrays become: $$$a = [1, 3, 2, 4]$$$, $$$b = [4, 3, 2, 2]$$$.
  • Choose index $$$1$$$, and set $$$a_1 := b_2$$$. The arrays become: $$$a = [3, 3, 2, 4]$$$, $$$b = [4, 3, 2, 2]$$$.
  • Choose index $$$1$$$, and set $$$b_1 := a_2$$$. The arrays become: $$$a = [3, 3, 2, 4]$$$, $$$b = [3, 3, 2, 2]$$$. Notice that you can perform $$$a_i := b_{i + 1}$$$ and $$$b_i := a_{i + 1}$$$ on the same index $$$i$$$.

The number of matches is $$$3$$$. It can be shown that this is the maximum answer we can achieve.

In the second test case, we can do the following to achieve a maximum of $$$3$$$:

  • Let's choose to remove index $$$5$$$. The arrays become: $$$a = [2, 1, 5, 3, 4]$$$, $$$b = [3, 2, 4, 5, 6]$$$.
  • Choose index $$$4$$$, and set $$$b_4 := a_5$$$. The arrays become: $$$a = [2, 1, 5, 3, 4]$$$, $$$b = [3, 2, 4, 4, 6]$$$.
  • Choose index $$$3$$$, and set $$$a_3 := b_4$$$. The arrays become: $$$a = [2, 1, 4, 3, 4]$$$, $$$b = [3, 2, 4, 4, 6]$$$.
  • Choose index $$$2$$$, and set $$$a_2 := b_3$$$. The arrays become: $$$a = [2, 4, 4, 3, 4]$$$, $$$b = [3, 2, 4, 4, 6]$$$.
  • Choose index $$$1$$$, and set $$$b_1 := a_2$$$. The arrays become: $$$a = [2, 4, 4, 3, 4]$$$, $$$b = [4, 2, 4, 4, 6]$$$.
  • Choose index $$$2$$$, and set $$$b_2 := a_3$$$. The arrays become: $$$a = [2, 4, 4, 3, 4]$$$, $$$b = [4, 4, 4, 4, 6]$$$.
  • Choose index $$$1$$$, and set $$$a_1 := b_2$$$. The arrays become: $$$a = [4, 4, 4, 3, 4]$$$, $$$b = [4, 4, 4, 4, 6]$$$.

In the third test case, it can be shown that we can not get any matches. Therefore, the answer is $$$0$$$.