The Repeater (Large)

Interview

Time limit5sMemory limit512 MB

Summary

Decide whether N lowercase strings can be made identical by duplicating or deleting adjacent equal letters, and report the fewest moves.

Level: Medium5 of 10
Topics: String, Sorting, Math
Solved: No attempts yet

Problem

Fegla and Omar play games every day. They are bored with every game they know, so they invented one of their own and called it "The Repeater".

It is a game for two players. Fegla writes down $N$ strings. Omar has to make all the strings identical using the smallest possible number of moves, and he may use zero moves. Only these two moves are allowed.

Pick any character in any of the strings and repeat it, adding another copy of that character directly after it. For example, one move changes "abc" into "abbc" by repeating the character 'b'.
Pick any two adjacent identical characters in any of the strings and delete one of them. For example, one move changes "abbc" into "abc", but it cannot change it into "bbc".

The two moves are independent. A move of the first type does not have to be followed by a move of the second type, and the other way round.

Help Omar win: decide whether the given strings can be made identical, and if they can, report the minimum number of moves.

Input

The first line contains the number of test cases $T$ . $T$ test cases follow. Each test case starts with a line holding the number of strings $N$ , followed by $N$ lines with one string each. Every string is non-empty and consists of lower case English letters 'a' to 'z' only.

Limits

$1 \le T \le 100$
$2 \le N \le 100$
The length of each string is at least 1 and at most 100.

Output

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the minimum number of moves that makes all the strings identical. If there is no way to make them identical, print Fegla Won in place of $y$ .

Examples5

Example 1

Input

5
2
mmaw
maw
2
gcj
cj
3
aaabbb
ab
aabb
2
abc
abc
3
aabc
abbc
abcc

Expected output

Case #1: 1
Case #2: Fegla Won
Case #3: 4
Case #4: 0
Case #5: 3

Example 2
Input
```
1
2
a
aaaaa
```
Expected output
```
Case #1: 4
```

Example 3

Input

4
2
a
b
2
ab
ba
2
abc
abcd
3
aab
aab
abb

Expected output

Case #1: Fegla Won
Case #2: Fegla Won
Case #3: Fegla Won
Case #4: 2

Example 4

Input

1
100
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z
z

Expected output

Case #1: 0

Example 5

Input

3
4
a
a
aaaaa
aaaaa
4
ab
aaabbbb
aab
abbb
2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
a

Expected output

Case #1: 8
Case #2: 8
Case #3: 99