리피터

Fegla와 Omar는 매일 게임을 즐긴다. 하지만 이제 모든 게임에 싫증이 나서 새로운 게임을 하고 싶어 한다. 그래서 "The Repeater"라는 자신들만의 게임을 만들기로 했다.

그들은 2인용 게임을 만들었다. Fegla는 N개의 문자열을 적는다. Omar의 임무는 가능하다면 다음 두 가지 유형의 행동을 최소 횟수로(행동 횟수는 0일 수도 있다) 수행하여 모든 문자열을 동일하게 만드는 것이다.

• 문자열 중 하나에서 임의의 문자를 선택하여 반복한다(그 문자 바로 뒤에 같은 문자를 하나 더 추가한다). 예를 들어 Omar는 한 번의 행동으로 "abc"를 "abbc"로 바꿀 수 있다('b' 문자를 반복한다).

• 문자열 중 하나에서 서로 인접하며 동일한 임의의 두 문자를 선택하고, 그중 하나를 삭제한다. 예를 들어 Omar는 한 번의 행동으로 "abbc"를 "abc"로 바꿀 수 있지만('b' 문자 중 하나를 삭제한다), "bbc"로 바꿀 수는 없다.

2 행동은 서로 독립적이다. 첫 번째 유형의 행동 뒤에 두 번째 유형의 행동을 해야 할 필요는 없다(그 반대도 마찬가지이다).

주어진 문자열들을 동일하게 만들 수 있는지, 그리고 가능하다면 최소 이동 횟수를 구하는 프로그램을 작성하여 Help Omar 이 게임에서 승리하도록 하라.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ 각 문자열의 길이 ≤ 100.

작은 데이터 세트

시간 제한: 60초. N = 2.

큰 데이터 세트

시간 제한: 120초. 2 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열의 수를 나타내는 정수 N이 포함된 줄로 시작한다. 그다음 N개의 줄이 주어지며, 각 줄에는 비어 있지 않은 문자열 하나가 포함된다(각 문자열은 'a'부터 'z'까지의 영문 소문자로만 구성된다).

각 테스트 케이스마다 "Case #x: y"이 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 문자열들을 동일하게 만드는 데 필요한 최소 이동 횟수이다. 모든 문자열을 동일하게 만들 수 있는 방법이 없다면 "Fegla Won"을 출력한다(따옴표는 명확성을 위한 것이다).