Tiền tố DNA

Tại một phòng thí nghiệm sinh học nổi tiếng, nhà khoa học trẻ Alex đang thực hiện một dự án đột phá về gene di truyền. Alex có một bộ sưu tập gồm \(n\) mẫu DNA, mỗi mẫu là một chuỗi ký tự từ tập hợp \(\{A, C, G, T\}\). Để phục vụ cho nghiên cứu, Alex cần tìm một tập hợp con các mẫu DNA có đặc điểm rất đặc biệt: giá trị của độ dài tiền tố chung dài nhất của tập hợp con đó, nhân với số lượng mẫu trong tập hợp con, phải đạt giá trị tối đa.

Ví dụ, nếu Alex có các mẫu DNA sau:

• ACGT
• ACGTGCGT
• ACCGTGC
• ACGCCGT

Nếu Alex chọn tập hợp con chỉ có mẫu \ACGT\, kết quả sẽ là \(4 \times 1 = 4\).
Nếu anh ấy chọn \ACGT, ACGTGCGT, ACGCCGT\, tiền tố chung dài nhất là ACG có độ dài 3. Kết quả là \(3 \times 3 = 9\).
Nếu anh ấy chọn tất cả các mẫu \ACGT, ACGTGCGT, ACCGTGC, ACGCCGT\, tiền tố chung dài nhất là AC có độ dài 2. Kết quả là \(2 \times 4 = 8\).

Nhiệm vụ của bạn là giúp Alex tìm ra giá trị tối đa có thể nhận được từ bất kỳ tập hợp con nào của các mẫu DNA đã cho.

Input

• Dòng đầu tiên là số nguyên \(T\) \((T \le 10)\), biểu thị số lượng trường hợp thử nghiệm.
• Mỗi trường hợp bắt đầu bằng một dòng chứa số nguyên \(n\) \((1 \le n \le 50000)\) biểu thị số lượng mẫu DNA.
• Mỗi dòng trong số \(n\) dòng tiếp theo chứa một chuỗi không rỗng có độ dài không lớn hơn 50. Và các chuỗi chỉ chứa các ký tự từ \(\{A, C, G, T\}\).

Output

Đối với mỗi trường hợp, in ra một dòng duy nhất theo định dạng: "Case [số trường hợp]: [kết quả tối đa]", trong đó [số trường hợp] bắt đầu từ 1.

Example

3
4
ACGT
ACGTGCGT
ACCGTGC
ACGCCGT
3
CGCGCGCGCGCGCCCCGCCCGCGC
CGCGCGCGCGCGCCCCGCCCGCAC
CGCGCGCGCGCGCCCCGCCCGCTC
2
CGCGCCGCGCGCGCGCGCGC
GGCGCCGCGCGCGCGCGCTC

Case 1: 9
Case 2: 66
Case 3: 20