Trong tiếng Anh, có 26 chữ cái được chia thành nguyên âm hoặc phụ âm. Trong bài toán này, chúng ta coi a, e, i, o, và u là các nguyên âm, và 21 chữ cái còn lại là các phụ âm.

Một bộ lạc sống trong Khu rừng Đầy màu sắc Vĩ đại có truyền thống đặt tên cho các thành viên bằng các chữ cái tiếng Anh. Tuy nhiên, việc đặt một cái tên hay cho thành viên mới không hề dễ dàng vì nó phản ánh địa vị xã hội của thành viên đó trong bộ lạc. Người ta tin rằng tên càng ít phổ biến thì người sở hữu nó càng có nhiều đặc quyền xã hội.

Tộc trưởng của bộ lạc là một nhà ngôn ngữ học chuyên nghiệp. Ông nhận thấy rằng những cái tên khó phát âm thường ít phổ biến, và lý do là chúng có quá nhiều phụ âm liên tiếp. Do đó, ông thông báo rằng địa vị xã hội của một thành viên trong bộ lạc được xác định bởi giá trị \(n\) của cái tên đó, chính là số lượng chuỗi con có ít nhất \(n\) phụ âm liên tiếp trong tên. Ví dụ, khi \(n = 3\), cái tên "quartz" có giá trị \(n\) là 4 vì các chuỗi con quartz, uartz, artz, và rtz mỗi chuỗi đều có ít nhất 3 phụ âm liên tiếp. Giá trị \(n\) càng lớn nghĩa là địa vị xã hội trong bộ lạc càng cao. Hai chuỗi con được coi là khác nhau nếu chúng bắt đầu hoặc kết thúc ở các vị trí khác nhau (ngay cả khi chúng bao gồm các chữ cái giống nhau), ví dụ "tsetse" chứa 11 chuỗi con có hai phụ âm liên tiếp, mặc dù một số chuỗi trong đó (như "tsetse" và "tsetse") chứa các chữ cái giống nhau.

Tất cả các thành viên trong bộ lạc phải được tộc trưởng đặt tên và cho trước giá trị \(n\). Mặc dù tộc trưởng là một nhà ngôn ngữ học và có thể đảm bảo rằng các cái tên được đặt đều có ý nghĩa, nhưng ông không giỏi tính toán giá trị \(n\). Hãy giúp tộc trưởng xác định giá trị \(n\) của mỗi cái tên. Lưu ý rằng các cái tên khác nhau có thể có các giá trị \(n\) khác nhau đi kèm.

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. Dòng đầu tiên của mỗi bộ test cho biết tên của một thành viên dưới dạng một chuỗi có độ dài \(L\), và một số nguyên \(n\). Mỗi tên bao gồm một hoặc nhiều chữ cái tiếng Anh viết thường.

Dữ liệu ra

Với mỗi bộ test, hãy xuất 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à giá trị \(n\) của tên thành viên đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 < n \le L\).

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le L \le 100\).
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le L \le 10^6\). Kích thước tệp đầu vào không lớn hơn 6MB.

Đ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ụ

4
quartz 3
straight 3
gcj 2
tsetse 2

Case #1: 4
Case #2: 11
Case #3: 3
Case #4: 11

Nguồn

Google Code Jam 2013, Vòng 1C, bài Consonants.

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