编辑距离

给定两个长度分别为 n,mn,m 的字符串 A,BA,B。你每次可以对字符串 AA 执行以下三个操作之一：

删去任意一个字符 插入任意一个字符 选择任意一个字符，将其改成任意一个其他字符 请问将 AA 变得与 BB 相等，至少需要执行几次操作？

输入

本题有多组测试数据。第一行一个整数T代表测试数据组数。

对于每组数据，共三行，第一行输入两个整数 n,m接下来两行分别给出字符串A,B。

输出

对于每组数据，输出一行一个整数代表答案。

输入样例 1

5

7 5

sfdqxbw

gfdgw

1 1

a

b

1 2

a

aa

2 1

aa

a

50 32

yyrikdtoagaxnjkxfqshdplqsywxkeadekgymwodpwtrsjdhlw

lfjrskofqrglofpaqrvlenesyyrjwokp

输出样例 1

4

1

1

1

40

提示

样例解释 1：

sfdqxbw→gfdqxbw→gfdxbw→gfdbw→gfdgw。

对于 30%的数据，n,m≤6。

另有 20%的数据，满足 m≤3。

另有 20%的数据，满足字符串A,B仅包含a和b。

对于 100%的数据，满足 1≤T≤1000,max{n,m}≤3000。字符串A，B仅包含小写英文字符。

求大佬代码！！本人在线等