Fegla và Omar rất thích chơi trò chơi mỗi ngày. Nhưng giờ họ đã chán tất cả các trò chơi cũ và muốn chơi một trò chơi mới. Vì vậy, họ quyết định tự sáng tạo ra trò chơi của riêng mình mang tên "The Repeater" (Người lặp lại).

Họ đã phát minh ra một trò chơi dành cho 2 người. Fegla viết xuống \(N\) chuỗi ký tự. Nhiệm vụ của Omar là làm cho tất cả các chuỗi này trở nên giống hệt nhau, nếu có thể, bằng cách sử dụng số lượng thao tác ít nhất (có thể là 0 thao tác) thuộc hai loại sau:

• Chọn bất kỳ ký tự nào trong bất kỳ chuỗi nào và lặp lại nó (thêm một bản sao của ký tự này ngay sau nó). Ví dụ, trong một bước di chuyển, Omar có thể thay đổi "abc" thành "abbc" (bằng cách lặp lại ký tự 'b').
• Chọn bất kỳ hai ký tự kề nhau và giống hệt nhau trong bất kỳ chuỗi nào, và xóa một trong số chúng. Ví dụ, trong một bước di chuyển, Omar có thể thay đổi "abbc" thành "abc" (xóa một trong các ký tự 'b'), nhưng không thể biến nó thành "bbc".

Hai loại thao tác này là độc lập; không nhất thiết một thao tác loại thứ nhất phải được theo sau bởi một thao tác loại thứ hai (hoặc ngược lại).

Hãy giúp Omar thắng trò chơi này bằng cách viết một chương trình để tìm xem có thể làm cho các chuỗi đã cho trở nên giống hệt nhau hay không, và tìm số bước di chuyển tối thiểu nếu có thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\) là số lượng các chuỗi. Tiếp theo là \(N\) dòng, mỗi dòng chứa một chuỗi không rỗng (mỗi chuỗi sẽ chỉ bao gồm các ký tự tiếng Anh viết thường, từ 'a' đến 'z').

Dữ liệu ra

Với mỗi bộ test, hãy in ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số bước di chuyển tối thiểu để làm cho các chuỗi giống hệt nhau. Nếu không có cách nào để làm cho tất cả các chuỗi giống hệt nhau, hãy in "Fegla Won" (trong ngoặc kép để cho rõ ràng).

Ràng buộc

\(1 \le T \le 100\).
\(1 \le\) độ dài của mỗi chuỗi \(\le 100\).

Phân nhóm

• Small dataset: \(N = 2\).
• Large dataset: \(2 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

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

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

Nguồn

Google Code Jam 2014, Vòng 1B, bài The Repeater.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.