Edit Distance Transformation

You are given two strings A and B. Your task is to compute the minimum number of operations required to transform string A into string B. The permitted operations are insertion, deletion, and substitution.

This classical problem can be solved using dynamic programming. One common recurrence is given by:

$$dp[i][j] = \min\begin{cases} dp[i-1][j] + 1,\\ dp[i][j-1] + 1,\\ dp[i-1][j-1] + \mathbf{1}_{(A[i-1] \neq B[j-1])} \end{cases}$$

where $$\mathbf{1}_{(A[i-1] \neq B[j-1])}$$ equals 0 if the characters are equal, and 1 otherwise.

Please read input from standard input and write the answer to standard output.

inputFormat

The first line contains an integer T, the number of test cases. For each test case, the next two lines contain the strings A and B respectively. Note that strings may be empty.

outputFormat

For each test case, output a single line containing the minimum number of operations required to transform string A into string B.## sample

3
horse
ros
intention
execution
abc
abc

3
5
0