Вам заданы строки \(a\) и \(b\), состоящие из строчных букв латинского алфавита. Вы можете сделать произвольное число следующих операций в произвольном порядке:
- если \(|a| > 0\) (длина строки \(a\) больше нуля), удалить первый символ строки \(a\), то есть заменить \(a\) на \(a_2 a_3 \ldots a_n\);
- если \(|a| > 0\), удалить последний символ строки \(a\), то есть заменить \(a\) на \(a_1 a_2 \ldots a_{n-1}\);
- если \(|b| > 0\) (длина строки \(b\) больше нуля), удалить первый символ строки \(b\), то есть заменить \(b\) на \(b_2 b_3 \ldots b_n\);
- если \(|b| > 0\), удалить последний символ строки \(b\), то есть заменить \(b\) на \(b_1 b_2 \ldots b_{n-1}\).
Заметьте, что после каждой из операций строка \(a\) или \(b\) могут стать пустыми.
Например, если \(a=\)«hello» и \(b=\)«icpc», то вы можете применить следующую последовательность операций:
- удалить первый символ строки \(a\) \(\Rightarrow\) \(a=\)«ello» и \(b=\)«icpc»;
- удалить первый символ строки \(b\) \(\Rightarrow\) \(a=\)«ello» и \(b=\)«cpc»;
- удалить первый символ строки \(b\) \(\Rightarrow\) \(a=\)«ello» и \(b=\)«pc»;
- удалить последний символ строки \(a\) \(\Rightarrow\) \(a=\)«ell» и \(b=\)«pc»;
- удалить последний символ строки \(b\) \(\Rightarrow\) \(a=\)«ell» и \(b=\)«p».
По заданным строкам \(a\) и \(b\) найдите минимальное количество операций, за которые можно сделать строки \(a\) и \(b\) равными. Обратите внимание, что пустые строки также являются равными.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальное количество операций, за которые можно сделать строки \(a\) и \(b\) равными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser
|
0
2
13
3
20
|