Edit Distance Transformation

Given two strings, you are to compute the minimum number of operations required to transform the first string into the second string. The allowed operations are:

• Insertion
• Deletion
• Substitution

The problem can be solved using dynamic programming. The recurrence relation is given by:

$$ \begin{aligned} 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] = s_2[j] \\ 1 + \min\{dp[i][j-1],\; dp[i-1][j],\; dp[i-1][j-1]\}, & \text{otherwise} \end{cases} \end{aligned} $$

Where \(dp[i][j]\) represents the minimum operations required to convert the first \(i\) characters of the first string to the first \(j\) characters of the second string.

inputFormat

The input is read from stdin and consists of multiple test cases.

The first line contains an integer T, the number of test cases. Each test case consists of two lines: the first line contains the first string, and the second line contains the second string.

For example:

5
horse
ros
intention
execution
abcd
abc
abc
abc
abc
def

outputFormat

For each test case, output the minimum number of operations needed to transform the first string into the second string. Each result should be printed on a new line to stdout.

For the sample input above, the output should be:

3
5
1
0
3

## sample

5
horse
ros
intention
execution
abcd
abc
abc
abc
abc
def

3
5
1
0
3

</p>