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

Вам заданы строки $$$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$$$ равными. Обратите внимание, что пустые строки также являются равными.

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$). Далее следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит строку $$$a$$$ ($$$1 \le |a| \le 20$$$), состоящую из строчных букв латинского алфавита.

Вторая строка каждого набора входных данных содержит строку $$$b$$$ ($$$1 \le |b| \le 20$$$), состоящую из строчных букв латинского алфавита.

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

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

Пример
Входные данные
5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser
Выходные данные
0
2
13
3
20