Minimum Edit Distance Transformation

You are given two strings S and T. Your task is to compute the minimum number of operations required to transform S into T. The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Substitution of a single character

This is equivalent to finding the Levenshtein distance between the two strings. The dynamic programming recurrence used is as follows:

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

Given multiple test cases, for each test case, you will be given two strings. You must output the result for each test case on a separate line.

inputFormat

The input is given via standard input and has the following format:

T
S1
T1
S2
T2
... 
ST
TT

Where T (an integer) is the number of test cases, and for each test case, one string S is given on one line followed by the string T on the next line.

outputFormat

For each test case, print a single integer on a separate line indicating the minimum number of operations required to transform S into T.

## sample

3
horse
roses
intention
execution
abc
abc

3
5
0

</p>