Minimum Edit Distance

You are given two strings s1 and s2. Your task is to compute the minimum edit distance between them, i.e. the minimum number of operations required to transform s1 into s2. The permitted operations are:

• Insertion
• Deletion
• Substitution

This problem is based on the well known Levenshtein distance algorithm. In mathematical terms, the recurrence relation is given by:

$$dp[i][j] = \min\begin{cases} dp[i-1][j] + 1,\\ dp[i][j-1] + 1,\\ dp[i-1][j-1] + \begin{cases} 0 & \text{if } s1[i-1]=s2[j-1] \\ 1 & \text{otherwise} \end{cases} \end{cases}$$

You need to process multiple test cases.

inputFormat

The first line of the input contains an integer T, the number of test cases. Each test case consists of two lines: the first line contains the string s1 and the second line contains the string s2.

outputFormat

For each test case, output a single line containing the minimum edit distance between the two given strings.

## sample

2
horse
ros
intention
execution

3
5

</p>