Minimum Edit Distance

Problem Description:

Given two strings (s_1) and (s_2), calculate the minimum edit distance required to transform (s_1) into (s_2). The allowed operations are insertion, deletion, and substitution. These operations have equal cost. The edit distance can be computed using dynamic programming with the recurrence:

[ \displaystyle dp[i][j] = \begin{cases} j, & \text{if } i = 0,\ i, & \text{if } j = 0,\ dp[i-1][j-1], & \text{if } s_1[i-1] = s_2[j-1],\ 1 + \min{dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]}, & \text{otherwise.} \end{cases} ]

You are given (T) test cases. For each test case, compute and output the minimum number of operations required to transform the first string into the second string.

inputFormat

Input Format:

The first line contains an integer (T), the number of test cases. Each of the next (T) lines contains two strings separated by a single space. Note that the strings may be empty.

outputFormat

Output Format:

For each test case, output the minimum edit distance (an integer) on a new line.## sample

3
abc abd
intention execution
abc abc

1
5
0