String Transformation

You are given two strings, \(A\) and \(B\). Your task is to compute the minimum number of operations required to transform string \(A\) into string \(B\). The allowed operations are:

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

Each operation has a cost of 1. This problem is a classic example of computing the edit distance between two strings using dynamic programming.

The edit distance \(D(A,B)\) is defined by the recurrence:

[ D(i,j)=\begin{cases} j & \text{if } i=0\ i & \text{if } j=0\ D(i-1,j-1) & \text{if } A_i = B_j\ 1+\min{D(i,j-1),;D(i-1,j),;D(i-1,j-1)} & \text{otherwise} \end{cases} ]

Compute \(D(|A|,|B|)\) where \(|A|\) and \(|B|\) are the lengths of strings \(A\) and \(B\) respectively.

inputFormat

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

1. The first line contains the source string \(A\).
2. The second line contains the target string \(B\).

outputFormat

For each test case, output a single line containing the minimum number of operations needed to transform \(A\) into \(B\).

## sample

2
abcdef
azced
short
ports

3
3

</p>