Description

For two different strings, we have a set of operations to make them identical. The specific methods are:

• Modify a character (e.g., replace "a" with "b");
• Delete a character (e.g., change "traveling" to "travelng").

For example, for the two strings "abcdefg" and "abcdef", we consider that the goal can be achieved by adding/removing a "g". Whether adding or removing "g", we only need one operation. We define the number of operations required as the distance between the two strings.

Given any two strings, write an algorithm to calculate their distance.

Input Format

The first line contains an integer n, representing the number of test cases.
The next n lines each contain two strings separated by a space, representing the pair of strings for which the distance is to be calculated. The length of each string does not exceed 1000.

Output Format

For each test case, output an integer representing the distance between the two strings.

3
abcdefg  abcdef
ab ab
mnklj jlknm

1
0
4