The Repeater

Interview

Time limit5sMemory limit512 MB

Summary

Equalize N lowercase strings using only adjacent duplicate insertions and deletions with the fewest moves, or report impossibility.

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

Problem

Fegla and Omar play games every day. They got bored of every game they knew, so they invented a new one and named it "The Repeater".

It is a game for two players. Fegla writes down $N$ strings. Omar has to make all of the strings identical using only the two moves below, and he has to use as few moves as possible, possibly 0 moves.

Pick any character in any of the strings and repeat it, adding one more copy of that character directly after it. For example, one move changes "abc" into "abbc" by repeating the '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" by deleting one 'b', but it cannot change "abbc" 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 around.

Help Omar win. Write a program that decides whether the strings can be made identical and, when they can, reports 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 containing the number of strings $N$ , followed by $N$ lines with one string per line. Each string is non-empty and consists of lower case English letters 'a' to 'z' only.

Limits

$1 \le T \le 100$
The length of each string is between 1 and 100
$2 \le N \le 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 the strings identical. If the strings cannot be made identical, print Fegla Won in place of $y$ . Do not print the double quotes.

Examples4

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
a
```
Expected output
```
Case #1: 0
```

Example 3

Input

1
3
abcdefghijklmnopqrstuvwxyz
aaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzz

Expected output

Case #1: 52

Example 4

Input

1
2
abababababababababababababababababababababababababababababababababababababababababababababababababab
abababababababababababababababababababababababababababababababababababababababababababababababababab

Expected output

Case #1: 0