给定两个整数数组 $$$a$$$ 和 $$$b$$$,每个数组的长度为 $$$n$$$。
您可以多次执行以下操作:
- 选择索引 $$$i$$$ $$$(1 \le i \le n - 1)$$$,并设置 $$$a_i := b_{i + 1}$$$, or 设置$$$b_i := a_{i + 1}$$$。
之前 执行任何操作时,您可以选择索引 $$$i$$$ $$$(1 \le i \le n)$$$ 并从数组中删除 $$$a_i$$$ 和 $$$b_i$$$ 。可以进行此删除操作 最多一次.
设长度为 $$$m$$$ 的两个数组 $$$c$$$ 和 $$$d$$$ 之间的匹配数为位置数 $$$j$$$ $$$(1 \le j \le m)$$$,使得 $$$c_j = d_j$$$。
您的任务是计算您可以实现的最大匹配数。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。每个测试用例的描述如下。
第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — $$$a$$$ 和 $$$b$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$ — $$$a$$$ 的元素。
第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le n)$$$ — $$$b$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 测试用例的答案。
示例
输入复制
1041 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 4
输出复制
3 3 0 4 3 5 6 4 5 2
注意
在第一个测试用例中,我们可以执行以下操作:
- 我们将选择不删除任何索引。
- 选择索引 $$$3$$$,并设置 $$$a_3 := b_4$$$。数组变为:$$$a = [1, 3, 2, 4]$$$,$$$b = [4, 3, 2, 2]$$$。
- 选择索引 $$$1$$$,并设置 $$$a_1 := b_2$$$。数组变为:$$$a = [3, 3, 2, 4]$$$,$$$b = [4, 3, 2, 2]$$$。
- 选择索引 $$$1$$$,并设置 $$$b_1 := a_2$$$。数组变为:$$$a = [3, 3, 2, 4]$$$,$$$b = [3, 3, 2, 2]$$$。请注意,您可以在同一索引 $$$i$$$ 上执行 $$$a_i := b_{i + 1}$$$ 和 $$$b_i := a_{i + 1}$$$。
匹配数为 $$$3$$$。可以证明,这是我们能得到的最大答案。
在第二个测试用例中,我们可以执行以下操作来实现最大值 $$$3$$$:
- 让我们选择删除索引 $$$5$$$。数组变为:$$$a = [2, 1, 5, 3, 4]$$$,$$$b = [3, 2, 4, 5, 6]$$$。
- 选择索引 $$$4$$$,并设置 $$$b_4 := a_5$$$。数组变为:$$$a = [2, 1, 5, 3, 4]$$$,$$$b = [3, 2, 4, 4, 6]$$$。
- 选择索引$$$3$$$,并设置$$$a_3 := b_4$$$。数组变为:$$$a = [2, 1, 4, 3, 4]$$$,$$$b = [3, 2, 4, 4, 6]$$$。
- 选择索引$$$2$$$,并设置$$$a_2 := b_3$$$。数组变为:$$$a = [2, 4, 4, 3, 4]$$$,$$$b = [3, 2, 4, 4, 6]$$$。
- 选择索引$$$1$$$,并设置$$$b_1 := a_2$$$。数组变为:$$$a = [2, 4, 4, 3, 4]$$$,$$$b = [4, 2, 4, 4, 6]$$$。
- 选择索引$$$2$$$,并设置$$$b_2 := a_3$$$。数组变为:$$$a = [2, 4, 4, 3, 4]$$$,$$$b = [4, 4, 4, 4, 6]$$$。
- 选择索引$$$1$$$,并设置$$$a_1 := b_2$$$。数组变为:$$$a = [4, 4, 4, 3, 4]$$$,$$$b = [4, 4, 4, 4, 6]$$$。
在第三个测试用例中,可以表明我们无法获得任何匹配项。因此,答案是$$$0$$$。