题目描述

给定两个字符串。每次可以插入一个字符、删除一个字符，或修改一个字符。两个字符串的距离是把一个字符串变为另一个字符串所需的最少操作次数。

请分别计算每组字符串的距离。

输入格式

第一行一个整数T，表示数据组数。接下来T行，每行两个字符串。

输出格式

每组数据输出一行一个整数，表示两个字符串的距离。

样例

3
abcdefg abcdef
ab ab
mnklj jlknm

1
0
4

数据范围

1≤T≤10；字符串仅包含小写字母，长度为1至1000。