5435번 - Polly Wants a Cracker 다국어

In the pirate society, each pirate captain is obligated to obtain a pet. This pet should be at the side (or on the shoulder) of a pirate captain at all times, especially during conversations with good doers who wish to challenge the captain’s evil ways.

Greedbeard is the infamous and feared captain of the pirate ship Greatlooter. His pet is the infamous and feared parrot known as Polly. As a parrot, Polly likes to mimic the conversations he overhears. Unfortunately, Polly is not very good at mimicking the sentences he hears. For this reason, Greedbeard has taken it upon himself to assist Polly as he learns to speak the human tongue.

Greedbeard noted that Polly is able to speak whole sentences, but often makes one or more of the three following mistakes:

1. Polly mixes up the sentence by placing words in the wrong order. E.g. instead of saying “polly wants a cracker”, Polly will say “polly cracker a wants”;
2. Polly forgets some words in a sentence. E.g. instead of saying “polly wants a cracker”, Polly will say “polly a cracker”;
3. Finally, Polly mixes up, adds or removes consonants and vowels² in his words. So instead of saying “polly wants a cracker”, Polly will say “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 mimic.

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, each time Polly makes mistakes in a sentence by mixing up letters, the captain will take away one cracker from his lunch, for each letter he mixes up. The number of crackers that the captain removes per word, is the minimum number of edits needed to transform the spoken word into the word that Polly was trying to say. An edit is defined as either an insertion, deletion or substitution of a single letter.

It is not always clear how words in the mimicked sentence correspond to words in the original sentence. Greedbeard assumes the mimicked words are matched with the original words in such a way that the total number of mistakes is minimal.

For instance, if Polly should have said: “polly wants a cracker” and says: “polly crackets wantsu”, the captain will remove 3 crackers from his lunch. These are 2 crackers for messing up the word “cracker” and 1 cracker for adding a letter to the word “wants”. He does not care that the word “a” is missing, or that words are spoken in the wrong order.

²Read: mixes up, adds or removes letters

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• A line containing a single string (1 ≤ length ≤ 1000), representing the sentence that Polly is trying to mimic;
• A line containing a single string (1 ≤ length ≤ 1000), the sentence that Polly has spoken.

Additional notes:

• The sentence Polly mimics consists of one to eight words.
• A word is a sequence of lowercase letters. Each word ends with a space, or with the end of the sentence.
• A sentence does not contain a sequence of multiple spaces.

For every test case in the input, the output should contain one integer on a single line: the number of crackers that Greedbeard will withhold from Polly’s lunch.