题目内容

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

在这个项目中，有两个字符串 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$ 。