Minimum Edit Distance

This problem requires you to compute the minimum edit distance between two strings. The edit distance is defined as the minimum number of operations required to transform the first string into the second string using insertion, deletion, or replacement of a single character.

You can solve the problem using dynamic programming. The recurrence relation is given by:

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

Your task is to implement this function so that for each test case, you output the minimum edit distance.

inputFormat

The input is from standard input (stdin) and has the following format:

• The first line contains a single integer T representing the number of test cases.
• For each test case, there are two lines:
• The first line contains the string start.
• The second line contains the string goal.

Note that the strings consist of lowercase letters only and do not contain spaces.

outputFormat

For each test case, output a single integer representing the minimum number of edit operations required to transform start into goal. Each result should be printed on a new line to standard output (stdout).

## sample

3
kitten
sitting
abcd
abef
abc
def

3
2
3

</p>