Minimum Edit Distance

Given two strings \(A\) and \(B\), your task is to compute the minimum number of operations required to convert \(A\) into \(B\) using the following three operations:

• Insertion
• Deletion
• Replacement

Each operation has a cost of 1. The optimal solution can be computed using dynamic programming. 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 } A[i-1]=B[j-1] \\1 & \text{otherwise}\end{cases} \end{cases}\)

Your program should read multiple test cases from standard input and output the answer for each case on a new line.

inputFormat

The input is given from standard input as follows:

1. The first line contains an integer \(T\), the number of test cases.
2. Each of the next \(T\) lines contains two space-separated strings \(A\) and \(B\).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of edit operations required to convert string \(A\) into string \(B\).

## sample

4
abc yabd
intention execution
kitten sitting
a b

2
5
3
1

</p>