Polly Wants a Cracker#3116
In pirate society, there is a rule that every captain must have a pet. This animal should always be on the captain's shoulder, especially when talking to good heroes who challenge his evil deeds.
Greedbeard is one of the most infamous and dangerous captains of the pirate ship called Greatlooter. His pet is also infamous and dangerous—the parrot Polly. Like any parrot, Polly likes to imitate the conversations he hears. Unfortunately, Polly is not very good at copying the sentences he hears. Because of this, Greedbeard took it upon himself to help Polly as he learns to speak human language.
Greedbeard noticed that Polly is able to mimic whole sentences, but often makes one or more of the following three mistakes:
Polly mixes up the order of the words in the sentence. For example, instead of "polly wants a cracker", Polly says "polly cracker a wants";
Polly forgets some words from the sentence. For example, instead of "polly wants a cracker", Polly says "polly a cracker";
Finally, Polly mixes up, adds, or removes consonant and vowel letters^1 in his words. For example, instead of "polly wants a cracker", Polly says "polly wantsu a trackets".
Note that Polly never mimics the same word twice in a sentence. The captain always knows the original sentence that Polly is trying to imitate.
Captain Greedbeard is not interested in the first two mistakes. However, mixing up letters or adding/removing letters from a word makes his blood boil. Therefore, every time Polly makes a mistake in a word by changing letters, the captain takes one cracker from Polly's lunch for each letter changed. The number of crackers that the captain removes from Polly for a word is equal to the minimum number of edits needed to turn the word Polly says into the word he was supposed to say. An edit is defined as inserting, deleting, or replacing a letter.
It is not always clear how the words in Polly's spoken sentence correspond to the words in the original sentence. Greedbeard assumes that the words are matched so that the total number of mistakes is minimized.
For example, if Polly should have said: "polly wants a cracker", but says: "polly crackets wantsu", the captain takes 3 crackers from Polly's lunch: 2 crackers for the changes in "cracker" and 1 cracker for adding a letter to "wants". The captain does not care that the word "a" is missing or that the words are in the wrong order.
_______________
^1 Read: mixes up, adds, or removes letters.
The first line contains the number of tests. Each test has the following format:
a line ( length ) — the sentence Polly is trying to imitate;
a line ( length ) — the sentence Polly actually says.
Additional notes:
The imitated sentence consists of one to eight words.
A word is a sequence of lowercase letters. Each word ends with a space or the end of the sentence.
The sentence does not contain more than one space in a row.
For each test, output on a separate line the number of crackers Greedbeard will take from Polly's lunch.
Example 1