Даны три строки: \(a\), \(b\) и \(c\), состоящие из строчных латинских букв. Строка \(c\) была получена следующим образом:
- На каждом шаге случайно выбиралась строка \(a\) или строка \(b\), и первый символ выбранной строки удалялся из неё и приписывался в конец строки \(c\), пока одна из строк не заканчивалась. После этого оставшиеся символы непустой строки добавлялись в конец \(c\).
- Затем в строке \(c\) было произвольно изменено некоторое количество символов.
Например, из строк \(a=\color{red}{\text{abra}}\) и \(b=\color{blue}{\text{cada}}\) без замен символов могли получиться строки \(\color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}}\), \(\color{red}{\text{abra}}\color{blue}{\text{cada}}\), \(\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}\).
Найдите минимальное количество символов, которые могли быть изменены в строке \(c\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество символов, которые могли быть изменены в строке \(c\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg
|
1
0
2
0
3
2
3
|