Edit Distance Transformation

Given two strings \(S\) and \(T\), you are required to transform string \(S\) into string \(T\) using the minimum number of operations. The allowed operations are:

• Insert a character into \(S\).
• Delete a character from \(S\).
• Replace a character in \(S\) with another character.

The minimum number of operations required is equivalent to the Levenshtein distance between the two strings. The formula for computing the \(dp[i][j]\) element of the dynamic programming table is given by:

\[ \text{dp}[i][j] = \begin{cases} \text{dp}[i-1][j-1] & \text{if } S[i-1] = T[j-1] \\ \min\{\text{dp}[i-1][j]+1,\, \text{dp}[i][j-1]+1,\, \text{dp}[i-1][j-1]+1\} & \text{otherwise} \end{cases} \]

You need to solve multiple test cases. For each test case, read two strings and output the minimum number of operations required to convert \(S\) into \(T\).

inputFormat

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

Q
S1 T1
S2 T2
... 
SQ TQ

Where:

• Q: an integer representing the number of test cases.
• Each test case consists of two space-separated strings \(S\) and \(T\).

outputFormat

For each test case, output the minimum number of operations (edit distance) required to transform \(S\) into \(T\) on a new line. The output is written to stdout.

## sample

3
kitten sitting
flaw lawn
intention execution

3
2
5

</p>