잃어버린 비밀번호

아시시는 비밀번호를 잊어버렸다. 그는 비밀번호를 만들 때 다음 알고리즘을 사용했다는 것을 기억한다. 아시시는 글의 한 구절에서 최대 k개의 연속한 단어를 고르고, 각 단어의 첫 글자를 취했다. 그런 다음, 일부 글자를 그에 대응하는 "l33tspeak" 문자로 바꾸었을 수도 있다. 구체적으로, "o"를 "0"로, "i"를 "1"로, "e"를 "3"로, "a"를 "4"로, "s"를 "5"로, "t"를 "7"로, "b"를 "8"로, 그리고/또는 "g"를 "9"로 바꾸었을 수도 있다.

예를 들어, 아시시가 《반지 원정대》의 첫 문장인 -- "이 책은 주로 호빗에 관한 것이며, 독자는 이 책의 여러 페이지에서 그들의 성격에 관한 많은 것과 그들의 역사에 관한 약간의 것을 발견할 수 있다" -- 에서 비밀번호를 가져왔다면, 아시시는 이를 "tbilcwhafiparmdmotcaaloth"로 줄였을 것이다. 그러면 비밀번호는 "tbilcwh", "7b1lcwh4f", "a", "4", 또는 "4al07h" 등이 될 수 있다.

아시시의 브라우저에는 비밀번호가 포함된 어떤 문자열도 컴퓨터가 업로드하지 못하게 하는 특별한 확장 프로그램이 설치되어 있다. 자신이 어느 글의 구절에서 비밀번호를 가져왔는지 알아내기 위해, 아시시는 이 확장 프로그램을 활용하는 웹페이지를 만들었다. 매초 웹페이지는 새로운 글의 구절에 대한 "비밀번호 문자열"을 전송하도록 브라우저에 지시한다. 이 문자열은 아시시가 그 글의 구절에서 선택할 수 있었던 가능한 모든 비밀번호를 포함한다. 브라우저가 그러한 문자열을 전송하지 못하는 즉시, 아시시는 자신이 어디에서 비밀번호를 가져왔는지 알게 된다.

예를 들어, k = 2이고 글의 구절에 첫 글자가 "google"인 단어들이 포함되어 있다면, 그 구절에 대한 가능한 비밀번호 문자열 중 하나는 "goo0og00gle9o909l3"이다. 원래 문자열에서 길이가 ≤ 2인 모든 부분 문자열과, 그 모든 부분 문자열에 대응하는 l33tspeak 문자열이 새 문자열에 포함되어 있다.

글의 한 구절에 있는 단어들의 첫 글자가 주어질 때, 그 구절의 "비밀번호 문자열"에 필요한 최소 문자 수는 얼마인가?

제한

메모리 제한: 1GB. 테스트 세트당 시간 제한: 40초. 1 ≤ T ≤ 20. S에는 적어도 2 * k개의 문자가 포함된다. 최대 $10^{18}$개의 문자로 이루어진 비밀번호 문자열이 존재한다.

테스트 세트 1 (Visible Verdict)

S에는 최대 1000개의 문자가 포함된다. k = 2.

테스트 세트 2 (Hidden Verdict)

S에는 최대 5000개의 문자가 포함된다. 2 ≤ k ≤ 500.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 정수 k가 주어진다. 둘째 줄에는 글의 한 구절에 있는 단어들의 첫 글자를 나타내는 문자열 S가 주어진다. S는 공백 없이 'a' - 'z' 문자만 포함한다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작한다), y는 S에 대한 비밀번호 문자열의 최소 문자 수이다.

첫 번째 예제 입력에서 가능한 비밀번호 문자열 중 하나는 "0ppop0"이다. 두 번째 예제 입력에서 가능한 비밀번호 문자열 중 하나는 "goo0og00gle9o909l3"이다.