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

Даны три строки: $$$a$$$, $$$b$$$ и $$$c$$$, состоящие из строчных латинских букв. Строка $$$c$$$ была получена следующим образом:

  1. На каждом шаге случайно выбиралась строка $$$a$$$ или строка $$$b$$$, и первый символ выбранной строки удалялся из неё и приписывался в конец строки $$$c$$$, пока одна из строк не заканчивалась. После этого оставшиеся символы непустой строки добавлялись в конец $$$c$$$.
  2. Затем в строке $$$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$$$.

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

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

Первая строка каждого набора содержит одну строку из строчных латинских букв $$$a$$$ ($$$1 \leq |a| \leq 10^3$$$) — первая строка. Где $$$|a|$$$ обозначает длину строки $$$a$$$.

Вторая строка каждого набора содержит одну строку из строчных латинских букв $$$b$$$ ($$$1 \leq |b| \leq 10^3$$$) — вторая строка. Где $$$|b|$$$ обозначает длину строки $$$b$$$.

Третья строка каждого набора содержит одну строку из строчных латинских букв $$$c$$$ ($$$|c| = |a| + |b|$$$) — третья строка.

Гарантируется, что сумма $$$|a|$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$. Также сумма $$$|b|$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.

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

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

Пример
Входные данные
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