Ashish đã quên mật khẩu của mình. Anh ấy nhớ rằng mình đã sử dụng thuật toán sau để tạo mật khẩu: Ashish lấy tối đa \(k\) từ liên tiếp từ một đoạn văn bản và lấy chữ cái đầu tiên của mỗi từ. Sau đó, anh ấy có thể đã thay đổi một số chữ cái sang dạng "l33tspeak" tương đương. Cụ thể, anh ấy có thể đã thay đổi "o" thành "0", "i" thành "1", "e" thành "3", "a" thành "4", "s" thành "5", "t" thành "7", "b" thành "8" và/hoặc "g" thành "9".

Ví dụ, nếu Ashish lấy mật khẩu từ câu đầu tiên của cuốn The Fellowship of the Ring -- "This book is largely concerned with Hobbits, and from its pages a reader may discover much of their character and a little of their history" -- Ashish sẽ rút gọn nó thành "tbilcwhafiparmdmotcaaloth". Sau đó, mật khẩu có thể là "tbilcwh", "7b1lcwh4f", "a", "4", hoặc "4al07h", v.v.

Ashish có một tiện ích mở rộng đặc biệt được cài đặt trong trình duyệt của mình để ngăn máy tính tải lên bất kỳ chuỗi nào chứa mật khẩu của anh ấy. Để tìm ra đoạn văn bản nào anh ấy đã lấy mật khẩu, Ashish đã tạo một trang web để tận dụng tiện ích này. Mỗi giây, trang web sẽ yêu cầu trình duyệt gửi một "chuỗi mật khẩu" cho một đoạn văn bản mới: một chuỗi chứa tất cả các mật khẩu có thể mà Ashish có thể đã chọn từ đoạn văn bản đó. Ngay khi trình duyệt của anh ấy không gửi được chuỗi như vậy, Ashish sẽ biết mình đã lấy mật khẩu từ đâu.

Ví dụ, nếu \(k = 2\) và đoạn văn bản chứa các từ bắt đầu bằng các chữ cái "google", thì một chuỗi mật khẩu cho đoạn văn bản đó là "goo0og00gle9o909l3". Tất cả các chuỗi con có độ dài \(\le 2\) từ chuỗi gốc, và tất cả các biến thể l33tspeak tương đương của chúng, đều được chứa trong chuỗi mới này.

Cho các chữ cái đầu tiên của các từ trong một đoạn văn bản, số ký tự tối thiểu trong "chuỗi mật khẩu" của đoạn văn bản đó là bao nhiêu?

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\). \(T\) bộ test theo sau. Mỗi bộ test gồm hai dòng. Dòng đầu tiên chứa số nguyên \(k\). Dòng thứ hai chứa một chuỗi \(S\), đại diện cho các chữ cái đầu tiên của các từ trong một đoạn văn bản. \(S\) chỉ chứa các ký tự 'a' - 'z', không có khoảng trắng.

Dữ liệu ra

Đối 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à số ký tự tối thiểu trong chuỗi mật khẩu cho \(S\).

Ràng buộc

• \(1 \le T \le 20\).
• \(S\) sẽ chứa ít nhất \(2 \times k\) ký tự.
• Sẽ tồn tại một chuỗi mật khẩu với tối đa \(10^{18}\) ký tự.

Phân nhóm

• Test set 1 (Visible Verdict): \(S\) chứa tối đa 1000 ký tự; \(k = 2\).
• Test set 2 (Hidden Verdict): \(S\) chứa tối đa 5000 ký tự; \(2 \le k \le 500\).

Đ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
2
poppop
2
google
2
tbilcwhafiparmdmotcaaloth
10
tbilcwhafiparmdmotcaaloth

Case #1: 6
Case #2: 18
Case #3: 53
Case #4: 1136

Nguồn

Google Code Jam 2012, Vòng 3, bài Lost Password.

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