E. Lost Soultime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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$$$.OutputFor each test case, print a single integer — the answer for the test case.ExampleInput1041 3 1 44 3 2 262 1 5 3 6 43 2 4 5 1 621 22 162 5 1 3 6 43 5 2 3 4 641 3 2 22 1 3 483 1 4 6 2 2 5 74 2 3 7 1 1 6 5105 1 2 7 3 9 4 10 6 86 2 3 6 4 10 5 1 7 953 2 4 1 52 4 5 1 372 2 6 4 1 3 53 1 6 5 1 4 254 1 3 2 53 2 1 5 4Output3
3
0
4
3
5
6
4
5
2
NoteIn 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$$$.