Problem D
Smart Phone
You have a very smart phone. Here is the user experience when entering a word:
-
You decide on the word you want to write.
-
You start typing it.
-
At some point, three suggestions appear. The list of suggestions never changes after it has first been presented, even if you keep typing.
You always only get three suggestions. This would mean that the suggestions would not always fit on the screen. However, when this happens they are read aloud by a text to speech plugin that cost $9.99. Yes, it reads all the suggestions for every character you enter until you take one of the suggestions.
Since it’s a very smart phone, you can only do the following:
-
Replace what you have written so far with one of the suggestions.
-
Hit the backspace button.
-
Enter a letter.
Each of these options takes one keypress. An example: you want to enter the text CAKEEATER. When the suggestions appear, you had gotten to CAK. Let’s say you decide to take the suggestion CAKEMONSTER, remove MONSTER and enter EATER. This would mean that you used 1+7+5=13 keypresses to get to the word CAKEEATER. The only time you would want to do this is when you want to annoy the cookie monster. Also, a lot of keypresses could have been avoided here if we had made different decisions.
Write a program that minimize the amount of keypresses given the current input, the desired word and the three suggestions from your very smart phone.
Input
The first line of the input consists of a single integer,
$T$, the number of test
cases.
For each test case there will be five lines:
-
The word you want to type.
-
What has been written so far.
-
Suggestion 1
-
Suggestion 2
-
Suggestion 3.
-
$1 \leq T \leq 50$
-
All line lengths will be greater than zero, and less than or equal to 25.
-
All lines consist of only uppercase characters from the English alphabet (A–Z).
Output
For each test case, output the minimum number of keypresses needed to get to the desired word.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 CAKEEATER CAK CAKEMONSTER CARNIVAL CAKEEATUR IDIOPEN HODOR KEG IPHONE FLUXCAPACITATOR |
5 11 |
