Problem description
One of the Engineer friends of John, Mr. Dev tried to develop an encryption algorithm which can send strings of words wirelessly between two devices connected through Wi-Fi. On completing the design of algorithm, John decides to test his algorithm on real devices. To test his algorithm on device, Dev sends some strings from one device to another. On matching the strings that were send and receive he found out some problems as mentioned below:- 
1.In a word somehow some alphabets are changed from lowercase to uppercase and from uppercase to lowercase.
2. Before, after or in between the alphabets of a word, sometimes one or more number of consonants, vowels or numbers (1 to 9) were added.
3. Some vowels or consonants are changed to any other alphabet. But no two consecutive vowels or consonants are changed in a word.
Now Dev wants to find out the efficiency of his algorithm. But before that he wanted to know the minimum number of edits needed to transform the received string into sent string. Dev decides to ignore 1st problem in calculating the number of edits. An edit is defined as either a deletion or substitution of a single alphabet.
 

Input
First line of input will be s, no of test strings. 
For each test string, the next two lines contains two strings, first  string will be original string that was sent by the sender device(i.e. the correct string) and the second string is the received string that was received by the receiver device(i.e the test strings in which you need to find the minimum number of edits w.r.t. the first string).


Output
For each test string output a single positive number that will be the number of edits calculated in that string.

Constraints

0 ≤ s ≤ 100
Length of any String <= 500

 

Example
Input:
2
He is a good programmer
hp is a pool Probgrammer
Program
prpgreamp

Output:
4
3
 

Explanation
For first string received, 4 edits need to be done (substituting ‘p’ to ‘e’ in ‘hp’, substituting ‘p’ to ‘g’ in ‘pool’, substituting ‘l’ to ‘d’ in ‘pool’ and removing extra ‘b’ in ‘probgrammer’) to transform the received string into sent string.
For second string received, 3 edits need to be done (removing ‘r’, substituting ‘p’ to ‘o’, removing ‘e’ and removing ‘p’ in ‘prpgreamp’) to transform the received string into sent string.
def d(s1,s2):
    if len(s1) > len(s2):
        s1,s2 = s2,s1
    distances = range(len(s1) + 1)
    for index2,char2 in enumerate(s2):
        newDistances = [index2+1]
        for index1,char1 in enumerate(s1):
            if char1 == char2:
                newDistances.append(distances[index1])
            else:
                newDistances.append(1 + min((distances[index1],
                                             distances[index1+1],
                                             newDistances[-1])))
        distances = newDistances
    return distances[-1]
t = input()
for i in range(t):
    s = raw_input().lower().split()
    r = raw_input().lower().split()
    dist = 0
    for i in range(len(s)):
        dist += d(s[i],r[i])
    print dist