String Distance

Problem Background

Special for beginners, ^_^

Problem Description

For two different strings, we have a set of operations to make them identical:

• Modify a character (e.g. replace a with b);
• Delete a character (e.g. turn traveling into travelng).

For example, for the two strings abcdefg and abcdef, we can add/remove a g to achieve the goal. 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 compute their distance.

Input Format

The first line contains an integer $n$, the number of test cases.

The following $n$ lines each contain two strings separated by a space, the two strings whose distance is to be computed.

The length of each string does not exceed $1000$.

Output Format

For each test case, output one integer: the distance between the two strings.

Sample Input 1

3
abcdefg  abcdef
ab ab
mnklj jlknm

Sample Output 1

1
0
4

Constraints

Time limit 1s, memory limit 1024KiB for each test case.