잃어버린 비밀번호 (라지)

아시시는 비밀번호를 잊어버렸다. 만드는 방법만 기억한다. 어떤 글에서 연속한 단어를 최대 k개 골라 각 단어의 첫 글자를 순서대로 이어 붙였고, 그다음 몇 글자를 l33t(리트) 표기로 바꿨을 수도 있다. 바꿀 수 있는 글자는 o를 0, i를 1, e를 3, a를 4, s를 5, t를 7, b를 8, g를 9로 바꾸는 여덟 가지다.

글에 등장하는 단어의 첫 글자를 순서대로 이어 붙인 문자열을 S라고 하자. 비밀번호는 S의 길이 1 이상 k 이하인 연속 부분 문자열을 하나 잡고, 그 안의 각 글자를 그대로 두거나 위 규칙에 따라 바꿔서 얻은 문자열이다.

예를 들어 아시시가 반지의 제왕 첫 문장 "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"에서 비밀번호를 골랐다면 S는 "tbilcwhafiparmdmotcaaloth"이다. 이때 비밀번호는 "tbilcwh", "7b1lcwh4f", "a", "4", "4al07h" 같은 문자열이 될 수 있다.

아시시의 브라우저에는 비밀번호를 부분 문자열로 포함하는 문자열의 업로드를 막는 확장 기능이 설치되어 있다. 아시시는 이 성질로 비밀번호의 출처를 찾으려고 웹페이지를 하나 만들었다. 이 페이지는 1초에 한 번씩 글 하나의 "비밀번호 문자열"을 브라우저가 전송하게 한다. 비밀번호 문자열은 그 글에서 아시시가 고를 수 있었던 모든 비밀번호를 부분 문자열로 포함하는 문자열이다. 전송이 처음 실패하는 순간, 아시시는 비밀번호를 어느 글에서 따왔는지 알게 된다.

예를 들어 k = 2이고 어떤 글의 단어 첫 글자가 차례대로 "google"이라면 "goo0og00gle9o909l3"은 그 글의 비밀번호 문자열이다. 원래 문자열에서 길이가 2 이하인 모든 연속 부분 문자열과 그 l33t 변형이 모두 이 문자열 안에 들어 있다.

S가 주어질 때, 그 글의 비밀번호 문자열이 가질 수 있는 최소 길이를 구하라.

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 정수 k가 주어지고, 둘째 줄에 문자열 S가 주어진다. S는 글에 등장하는 단어의 첫 글자를 순서대로 이어 붙인 문자열이며, 공백 없이 'a'부터 'z'까지의 소문자로만 이루어진다.

제한

• $1 \le T \le 20$
• S의 길이는 $2k$ 이상 5000 이하이다.
• $2 \le k \le 500$
• 길이가 $10^{18}$ 이하인 비밀번호 문자열이 항상 존재한다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 S에 대응하는 비밀번호 문자열의 최소 길이다.

k = 2, S = "poppop"일 때 "0ppop0"은 비밀번호 문자열이다.

k = 2, S = "google"일 때 "goo0og00gle9o909l3"은 비밀번호 문자열이다.