Taco Transformation

In this problem, you are given two strings s and t. Your task is to compute the minimum number of operations required to transform string s into string t by using the following allowed operations:

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

This is the classic edit distance problem, also known as the Levenshtein distance. Mathematically, if we denote the edit distance between s and t as \(D(s,t)\), then the recurrence relation is given by:

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

The problem gets its quirky title "Taco Transformation" as a playful reference to the transformation challenge, similar to turning one kind of taco into another.

inputFormat

The first line of input contains an integer T indicating the number of test cases. Each test case consists of two lines:

1. The first line contains the string s.
2. The second line contains the string t.

Note: The strings can be empty and will consist only of lowercase English letters.

outputFormat

For each test case, output a single line containing the minimum number of operations required to transform the string s into string t.

## sample

5
horse
ros
intention
execution
abc
yabc
abc
abcd
cat
dog

3
5
1
1
3

</p>