给定两个字符串 $$$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。