题目思路

思路：思维 + 贪心

当 $len(s) > len(t)$ ，$s$ 中第 $len(t) + 1$ 到 $len(s)$ 这些字符都必须删除。

接下来我们考虑 $[1, min(len(s, len(t)))]$ 的部分。 因为删除只能删除最后一个，所以删除一个字符前，必须删除其后面的所有字符，但是其后面的字符中，可能存在字符和 $t$ 中对应位置的字符相等。

题目内容

小美是一名优秀的软件工程师，他的公司最近接到了一个新项目，需要在短时间内实现一个新的字符串匹配功能。

在这个项目中，有两个字符串 S 和 T，需要将字符串 S 变换成字符串 T 的一个前缀。这个任务非常重要，因为它将决定整个项目的成功与否。

为了完成这个任务，小美开始进行了大量的研究和分析。他发现，每次操作可以修改 S 的一个字符，也可以删除一个 S 末尾的字符，这样才能将 S 变换成 T 的前缀。

现在小美需要写一段程序，来输出最少需要操作的次数。

输入描述

第一行一个正整数 $t$ ，表示数据组数；

对于每一组数据输入两行仅包含小写字母的字符串 S 和 T 。

$1\le S.length(),T.length()\le 5\times 10^4$ ， $1\le t \le10$

输出描述

对于每一组数据，输出一个整数，表示最少需要操作的次数。

样例

输入

2
aba
abb
abcd
efg

输出

1
4

样例解释

第一组数据，可以修改最后一个字母，使得 S=abb ，是 T 的一个前缀；

第二组数据，需要将 S 整个串删除，操作次数为 $4$ 。