Minimum Edit Distance

You are given two strings and you need to compute the minimum number of operations required to transform the first string into the second string. The allowed operations are:

• Insertion of a character
• Deletion of a character
• Replacement of a character

This is a classic dynamic programming problem. If we define a DP table dp where:

\( dp[i][j] = \min\{ dp[i-1][j] + 1,\, dp[i][j-1] + 1,\, dp[i-1][j-1] + \delta \} \)

where \( \delta = 0 \) if the i-th character of the first string is equal to the j-th character of the second string, and 1 otherwise, then dp[m][n] gives the answer for strings of length m and n.

Your task is to process multiple test cases.

inputFormat

The first line of input contains a single integer T, indicating 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. Note that the strings may be empty.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum edit distance required to transform the first string into the second string. All output should be written to standard output (stdout).

## sample

3
abc
ab
horse
ros
intention
execution

1
3
5

</p>