Minimum Edit Distance

Given two strings \(s\) and \(t\), your task is to compute the minimum number of operations required to convert string \(s\) into string \(t\). The allowed operations are:

• Insertion of a single character
• Deletion of a single character
• Replacement of a single character

This problem is a classic example of determining the edit distance between two strings. The edit distance is defined by the recurrence: \[ dp(i,j)= \begin{cases} j, & \text{if } i=0\\ i, & \text{if } j=0\\ dp(i-1,j-1), & \text{if } s_i = t_j \\ 1 + \min\{dp(i-1,j),\;dp(i,j-1),\;dp(i-1,j-1)\}, & \text{otherwise} \end{cases} \] where \(dp(i,j)\) is the minimum number of operations to convert the first \(i\) characters of \(s\) into the first \(j\) characters of \(t\).

You are to write a program that reads multiple test cases from standard input and outputs the corresponding minimum number of operations for each test case to standard output.

inputFormat

The first line of input contains an integer \(T\) (\(T \ge 1\)) representing the number of test cases. Each test case consists of two lines:

1. The first line contains the string \(s\), the source string.
2. The second line contains the string \(t\), the target string.

Note: The strings may be empty.

outputFormat

For each test case, output a single line containing an integer which is the minimum number of operations required to convert \(s\) to \(t\).

## sample

3
abc
yabd
sea
eat
teacher
ther

2
2
3

</p>