E. Потерянная душа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых массива $$$a$$$ и $$$b$$$, каждый длиной $$$n$$$.

Вы можете выполнять следующую операцию любое количество раз:

  • Выберите индекс $$$i$$$ $$$(1 \le i \le n - 1)$$$ и присвойте $$$a_i := b_{i + 1}$$$, или присвойте $$$b_i := a_{i + 1}$$$.

Перед выполнением любых операций вы можете выбрать индекс $$$i$$$ $$$(1 \le i \le n)$$$ и удалить как $$$a_i$$$, так и $$$b_i$$$ из массивов. Это удаление можно выполнить не более одного раза.

Пусть количество совпадений между двумя массивами $$$c$$$ и $$$d$$$ длиной $$$m$$$ равно количеству позиций $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — ответ для данного набора.

Пример
Входные данные
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
Выходные данные
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]$$$. Обратите внимание, что вы можете выполнить $$$a_i := b_{i + 1}$$$ и $$$b_i := a_{i + 1}$$$ на одном и том же индексе $$$i$$$.

Количество совпадений равно $$$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$$$.