Minimum Edit Distance Transformation

In this problem, you are given m pairs of strings. Your task is to determine the minimum cost (i.e. the minimum number of operations) required to transform the first string into the second string for each pair. The allowed operations are insertion, deletion, and replacement of a single character, each with a cost of 1.

A common method to solve this problem is to use dynamic programming. In particular, if we define

$$dp[i][j]$$

as the minimum cost to convert the first i characters of string s into the first j characters of string t, then the recurrence relation is given by

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

Your program should read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer m, the number of string pairs.
• For each of the m pairs, there are two consecutive lines. The first line of the pair contains the source string, and the second line contains the target string.

Note: The strings can be empty.

outputFormat

For each pair, output the minimum number of operations required to transform the source string into the target string. The output should be printed to standard output (stdout) with each result on a separate line.## sample

2
kitten
sitting
flaw
law

3
1

</p>