C. Игра с переворотом
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть две строки $$$S$$$ и $$$T$$$ одинаковой длины $$$n$$$, состоящие из строчных латинских букв. Игроки ходят по очереди, первой ходит Алиса.

В свой ход Алиса выбирает число $$$i$$$ от $$$1$$$ до $$$n$$$, одну из строк $$$S$$$ или $$$T$$$, а также любую строчную латинскую букву $$$c$$$, и заменяет $$$i$$$-й символ в выбранной строке на символ $$$c$$$.

Боб же в свой ход выбирает одну из строк $$$S$$$ или $$$T$$$, и переворачивает её. Более формально, Боб делает замену $$$S := \operatorname{rev}(S)$$$ или $$$T := \operatorname{rev}(T)$$$, где $$$\operatorname{rev}(P) = P_n P_{n-1} \ldots P_1$$$.

Игра длится до тех пор, пока строки $$$S$$$ и $$$T$$$ не равны. Как только строки становятся равны, игра моментально заканчивается.

Определим длительность игры как суммарное количество ходов, сделанных обоими игроками в процессе игры. Например, если всего Алиса сделала $$$2$$$ хода, а Боб — $$$1$$$ ход, то длительность такой игры равна $$$3$$$.

Цель Алисы — минимизировать длительность игры, а цель Боба — максимизировать длительность игры.

Чему будет равна длительность игры, при оптимальной игре обоих игроков? Можно показать, что игра завершится за конечное число ходов.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина строк $$$S$$$ и $$$T$$$.

Вторая строка каждого набора входных данных содержит строку $$$S$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Третья строка каждого набора входных данных содержит строку $$$T$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

Пример
Входные данные
7
5
abcde
abxde
5
hello
olleo
2
ab
cd
7
aaaaaaa
abbbbba
1
q
q
6
yoyoyo
oyoyoy
8
abcdefgh
hguedfbh
Выходные данные
1
2
3
9
0
2
6
Примечание

В первом наборе входных данных Алиса в свой ход может заменить третий символ строки $$$S$$$ на x. После чего обе строки станут равны «abxde» и игра завершится после одного хода. Так как цель Алисы закончить игру за минимальное число ходов, этот ход будет одним из оптимальных первых ходов для неё, и итоговый ответ равен $$$1$$$.

Во втором наборе входных данных Алиса в свой ход может заменить пятый символ строки $$$T$$$ на h. После этого хода $$$S =$$$ «hello», $$$T =$$$ «olleh». Далее ходит Боб. В свой ход он обязан перевернуть одну из строк. Если Боб выберет строку $$$S$$$, то после его хода обе строки будут равны «olleh», а если он выберет строку $$$T$$$, то после его хода обе строки будут равны «hello». Таким образом, после представленного первого хода Алисы игра гарантированно завершится через $$$2$$$ хода. Несложно показать, что стратегии, гарантирующей завершение игры менее чем за $$$2$$$ хода, у Алисы не существует. Итоговый ответ равен $$$2$$$.

В третьем наборе входных данных Алиса в свой первый ход может заменить второй символ строки $$$S$$$ на c. После этого хода $$$S =$$$ «ac», $$$T =$$$ «cd». Далее ходит Боб. Если Боб перевернёт строку $$$S$$$, то после его хода $$$S =$$$ «ca», $$$T =$$$ «cd». Тогда несложно видеть, что в этом случае Алиса может гарантированно закончить игру на $$$3$$$-м ходу, заменив второй символ строки $$$T$$$ на a, после чего обе строки станут равны «ca». Если же Боб перевернёт строку $$$T$$$, то после его хода $$$S =$$$ «ac», $$$T =$$$ «dc». В этом случае Алиса также может гарантированно закончить игру на $$$3$$$-м ходу, заменив первый символ строки $$$S$$$ на d, после чего обе строки станут равны «dc». Таким образом Алиса может гарантированно закончить игру за $$$3$$$ хода вне зависимости от ходов Боба. Можно показать, что меньше чем за $$$3$$$ хода, при оптимальной игре Боба, игра завершиться не может.

В пятом наборе входных данных строки $$$S$$$ и $$$T$$$ равны, а значит игра завершится, не начавшись, за $$$0$$$ ходов.