Minimum Edit Distance

You are given two strings s1 and s2. Your task is to compute the minimum number of operations required to convert s1 to s2. The allowed operations are:

• Insertion of a single character.
• Deletion of a single character.
• Substitution of one character for another.

The problem can be modeled using a dynamic programming approach. Define a 2D array \(dp\) where \(dp[i][j]\) represents the minimum number of operations required to convert the first \(i\) characters of s1 to the first \(j\) characters of s2. The recurrence is given by:

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

Input will be provided as multiple queries through standard input. For each query, your program should output the minimum number of operations on a new line.

inputFormat

The first line contains an integer Q, denoting the number of queries.

Then for each query, there are two lines:

• The first line contains the string s1.
• The second line contains the string s2.

Note: The strings can be empty.

outputFormat

For each query, output a single integer representing the minimum number of operations required to convert s1 to s2. Each answer should be printed on a separate line.

## sample

3
kitten
sitting
horse
ros
a
b

3
3
1

</p>