Description:

    小Q博士开发出了一个文本编辑器，这个文本编辑器每次操作可以在字符串任意位置插入一个字符或者任意删除一个字符或者将其中一个字符替换成另一个字符。
    小Q在用这个文本编辑器编辑文本时，经常会遇到刚刚输入的字符串并不是想要输入的那个字符串，于是他就想把刚输入的字符串变换成正确的字符串，可是他比较懒，想用最少的操作次数来完成这个任务。你能告诉他最少需要几次操作吗？

Input:

输入有多组数据，第一行是一个整数N，表示有N组数据。每组数据有两行字符串，每行字符串长度不超过100，第一行表示小Q刚输入的字符串，第二行表示 小Q想要输入的正确的字符串。

Output:

输出N行，第i行表示第i组数据的最少操作次数。

Sample Input:

2
a
a
a
abc

Sample Output:

0
2

Source:

kokopelli