真懒

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

最近,一个题目难住了我们帅气的阿镇。他每天写很多单词,但是由于阿镇比较粗心,所以经常写错单词。然而,有时他写错单词之后又不想重新把这个单词再写一遍。所以他想修改其中的字母或者划去其中的字母,他可以有以下的几种方法:

 1.他可以在这个单词中插入一个字母。

2他也可以删除一个字母。

 3.他可以将一个字母改写为另一个。

 例如,他写的字要“one”,但他写道,“two”。因此,他可以先删除两个字母“t”型和“w”(两个步骤)。他可以在结尾插入再两个字母”n”和”e”(两个步骤)。 这样,他需要4个步骤,以纠正错误的单词。另外他可以直接依次将”o””n””e”直接修改成”t””w””o” 共三个步骤。

 下面问题来了.求出他最少修改的步骤数目使得他的单词与原单词相同。

Input

第一行给出了测试用例t 。 然后的t行,每行包含两个单词。第一个是正确的单词,第二是他写的单词。(区分大小写)

Output

最少需要的步骤数目(与样例类似)每个结果占一行

Sample Input

INPUT
6
Words information
Int apple
Int int
However how
Howe how
I III

Sample Output

9
5
1
5
2
2

Hint

Source

Junhua Zhang

提交代码