Алиса и Боб играют в игру. У них есть две строки $$$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$$$.
Для каждого набора входных данных в отдельной строке выведите единственное целое число — длительность описанной игры, при оптимальной игре обоих игроков.
75abcdeabxde5helloolleo2abcd7aaaaaaaabbbbba1qq6yoyoyooyoyoy8abcdefghhguedfbh
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$$$ ходов.
| Codeforces Round 879 (Div. 2) |
|---|
| Закончено |
