Polly Wants a Cracker

In pirate society, every pirate captain is required to keep a pet. The pet must stay at the captain's side (or on the captain's shoulder) at all times, especially during arguments with do-gooders who want to challenge the captain's wicked ways.

Greedbeard is the infamous, feared captain of the pirate ship Greatlooter. His pet is the equally feared parrot named Polly. Like all parrots, Polly loves to mimic the conversations he overhears, but he is not very good at it. To help, Greedbeard is teaching Polly to speak the human tongue.

Polly can repeat whole sentences, but he often makes one or more of these three kinds of mistakes:

1. He shuffles the words into the wrong order. For example, instead of "polly wants a cracker" he might say "polly cracker a wants".
2. He forgets some words. For example, instead of "polly wants a cracker" he might say "polly a cracker".
3. He garbles individual words by inserting, deleting, or changing letters. For example, instead of "polly wants a cracker" he might say "polly wantsu a trackets".

Polly never mimics the same original word more than once, and the captain always knows the original sentence Polly is trying to say.

Greedbeard does not mind the first two kinds of mistake. But garbling the letters within a word makes his blood boil: for every word that Polly garbles, the captain removes one cracker from his lunch for each letter that is wrong. The number of crackers removed for a single word equals the minimum number of single-letter edits (insertions, deletions, or substitutions) needed to turn the spoken word into the original word it was meant to be.

It is not always obvious which spoken word corresponds to which original word. Greedbeard matches the spoken words to the original words so that the total number of edits is as small as possible, with each spoken word matched to a distinct original word.

For example, if the original sentence is "polly wants a cracker" and Polly says "polly crackets wantsu", the captain removes 3 crackers: 2 for garbling "cracker" into "crackets" and 1 for adding a letter to "wants". He does not care that "a" is missing or that the words are out of order.

Given the original and spoken sentences, determine the total number of crackers the captain will withhold.

The first line contains a single integer $T$, the number of test cases. Each test case consists of two lines:

• a line with the original sentence Polly is trying to mimic ($1 \le \text{length} \le 1000$);
• a line with the sentence Polly actually spoke ($1 \le \text{length} \le 1000$).

Notes:

• The original sentence contains between one and eight words.
• A word is a sequence of lowercase letters. Words are separated by a single space, and there are no leading, trailing, or repeated spaces.
• Polly never invents new words, so the spoken sentence has at most as many words as the original.

For each test case, print a single line with one integer: the number of crackers Greedbeard withholds. This is the minimum possible total number of single-letter edits over all ways of matching each spoken word to a distinct original word.