← 返回题目列表

Codeforces · 1989/B

B. 子串和子序列

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

给定两个字符串 $$$a$$$ 和 $$$b$$$,均由小写拉丁字母组成。

字符串的子序列是可以通过从原始字符串中删除几个(可能为零)字符来获得的字符串。字符串的子字符串是该字符串的连续子序列。

例如,考虑字符串 abac:

- a、b、c、ab、aa、ac、ba、bc、aba、abc、aac、bac 和 abac 是其子序列;
- a、b、c、ab、ba、ac、aba、bac 和 abac 是其子字符串。

您的任务是计算包含 $$$a$$$ 作为子字符串和 $$$b$$$ 作为子序列的字符串的最小可能长度。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个字符串 $$$a$$$ ($$$1 \le |a| \le 100$$$),由小写拉丁字母组成。

每个测试用例的第二行包含一个字符串 $$$b$$$ ($$$1 \le |b| \le 100$$$),由小写拉丁字母组成。

输出

对于每个测试用例,打印一个整数 - 包含 $$$a$$$ 作为子字符串和 $$$b$$$ 作为子序列的字符串的最小可能长度。

示例

输入 #1

5
aba
cb
er
cf
mmm
mmm
contest
test
cde
abcefg

输出 #1

4
4
3
7
7

注意

在下面的示例中,与等于 $$$b$$$ 的子序列对应的字符以粗体显示。

在第一个示例中,可能的答案之一是 caba。

在第二个示例中,可能的答案之一是 ercf。

在第三个示例中,可能的答案之一是 mmm。

在第四个示例中,可能的答案之一是竞赛。

在第五个示例中,可能的答案之一是 abcdefg。