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.

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

Idx	Name	Rating
A	False Alarm	800
B	Shrink	800
C	Cool Partition	1200
D	Retaliation	1200
E	Lost Soul	1600
F	Wildflower	1800
G	Omg Graph	1900
H	Incessant Rain	2500

Codeforces Round 1029 (Div. 3)