Minimum Edit Distance

You are given two strings s1 and s2. Your task is to compute the minimum number of operations required to convert s1 into s2. You are allowed to perform three operations on a string:

• Insertion of a single character
• Deletion of a single character
• Substitution of one character for another

This problem can be solved efficiently using dynamic programming. The recurrence relation is given in LaTeX below:

$$ \text{dp}[i][j] = \begin{cases} j, & \text{if } i = 0, \\ i, & \text{if } j = 0, \\ \text{dp}[i-1][j-1], & \text{if } s1[i-1] = s2[j-1], \\ 1 + \min\{\text{dp}[i][j-1],\; \text{dp}[i-1][j],\; \text{dp}[i-1][j-1]\}, & \text{otherwise}\\ \end{cases} $$

For each test case, you will be given two lines representing the two strings, and you should output the minimum number of operations required to transform the first string into the second.

inputFormat

The input begins with an integer T on the first line, representing the number of test cases. Each test case consists of two lines: the first line contains the string s1 and the second line contains the string s2.

outputFormat

For each test case, output a single line with an integer representing the minimum number of operations required to convert s1 into s2.

## sample

3
intention
execution
horse
ros
abc
def

5
3
3

</p>