Minimum Edit Distance

Given two strings s1 and s2, calculate the minimum number of operations required to convert s1 into s2. The allowed operations are:

• Insertion
• Deletion
• Replacement of a character

You can use the following recurrence relation in your solution:

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

The final answer is given by \( dp[m][n] \), where \( m \) and \( n \) are the lengths of s1 and s2 respectively.

Input is provided via standard input (stdin) and output should be printed to standard output (stdout).

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains two non-empty strings s1 and s2 separated by white space.

outputFormat

For each test case, output a single integer, the minimum number of operations required to convert s1 to s2, each on a new line.

## sample

3
kitten sitting
flaw law
intention execution

3
1
5

</p>