Edit Distance Conversion

You are given two strings A and B. Your task is to compute the minimum number of operations required to convert string A into string B.

The allowed operations are:

• Insert a character at any position.
• Delete a character from any position.
• Replace a character with another character.

The solution requires you to implement the classic Edit Distance (Levenshtein Distance) algorithm using dynamic programming.

For example, converting "sunday" to "saturday" requires 3 operations.

inputFormat

The input is received from standard input (stdin) and begins with a single integer T representing the number of test cases. Each test case consists of two lines; the first line contains the string A and the second line contains the string B.

Example:

5
sunday
saturday
kitten
sitting
abc
yabd
intention
execution
a
b

outputFormat

For each test case, output a single line containing the minimum number of operations required to convert string A into string B. The output should be written to standard output (stdout).

Example:

3
3
2
5
1

## sample

5
sunday
saturday
kitten
sitting
abc
yabd
intention
execution
a
b

3
3
2
5
1

</p>