Cho một tập hợp \(n\) mẫu \(DNA\), trong đó mỗi mẫu là một chuỗi chứa các ký tự từ \({A, C, G, T}\), chúng ta đang cố gắng tìm một tập hợp con các mẫu trong tập hợp, trong đó độ dài của tiền tố chung dài nhất nhân với số lượng mẫu trong tập con đó là tối đa.

Để cụ thể, hãy để các mẫu là:

1. \(ACGT\)
2. \(ACGTGCGT\)
3. \(ACCGTGC\)
4. \(ACGCCGT\)

Nếu lấy tập con \({ACGT}\) thì kết quả là \(4\) \((4 \times 1)\), nếu lấy \({ACGT, ACGTGCGT, ACGCCGT}\) thì kết quả là \(3 \times 3 = 9\) (vì \(ACG\) là tiền tố chung), nếu lấy \({ACGT, ACGTGCGT, ACCGTGC, ACGCCGT}\) thì kết quả là \(2 \times 4 = 8\).

Yêu cầu:

• Báo cáo kết quả tối đa mà chúng ta có thể nhận được từ các mẫu.

Dữ liệu vào

• Dòng đầu 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ứa các ký tự từ \({A, C, G, T}\).

Dữ liệu ra

• Đối với mỗi trường hợp, in số trường hợp và kết quả tối đa có thể nhận được.

Input 1

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

Output 1

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