CF2117E Lost Soul

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.

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

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

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