← 返回题目列表

Codeforces · 1506/C

C. 双端弦

中文机器翻译题面 查看原题

给出字符串 $$$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$$$ 相等的最少操作数。

示例

输入 #1

5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser

输出 #1

0
2
13
3
20