题目思路

思路：思维 + 贪心

当 $len(A) > len(B)$ 时，$A$ 中从第 $len(B)+1$ 个到最后一个字符都必须删除。

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

题目内容

给定两个由小写字母构成的字符串 $A$ 和 $B$。每次操作你可以选择以下两种方式之一：

• 修改 $A$ 中的任意一个字符为任意小写字母；
• 删除 $A$ 的最后一个字符（若 $A$ 非空）。

你的目标是通过若干次操作，使得最终的 $A$ 成为 $B$ 的一个前缀（空串视为任何字符串的前缀）。请求出最少需要的操作次数。

约束：字符串长度均不超过 5*10^4，数据组数 $t$ 满足 $1 \le t \le 10$。

输入描述

第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试数据的组数。接下来每组数据包含两行，第一行为字符串 $A$，第二行为字符串 $B$。字符串均由小写字母构成，长度均不超过 5*10^4。

输出描述

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

样例1

输入

1
abc
abc

输出

0

说明

字符串 $A$ 与 $B$ 完全相同，已经满足是 $B$ 的前缀，因此不需要任何操作，最少操作次数为 0。

样例2

输入

1
abcd
abc

输出

1

说明

$A$ 的长度为 4，$B$ 的长度为 3。$A$ 的前三个字符 abc 与 $B$ 完全匹配，多余的字符 d 只能通过「删除最后一个字符」的方式去除，删除 1 次即可使 $A$ 成为 $B$ 的前缀。最少操作次数为 1。

样例3

输入

1
ab
ac

输出

1

说明

$A$ 和 $B$ 长度相同，但第二个字符不同（b 与 c）。可以花费 1 次操作将 $A$ 的第二个字符修改为 c，也可以删除最后一个字符使 $A$ 变为 a，同样花费 1 次操作。两种方式的最少操作次数均为 1。