잃어버린 비밀번호

아시시는 자신의 비밀번호를 잊어버렸다. 만드는 방법만은 기억한다. 어떤 글에서 연속한 단어를 최대 $k$개 골라 각 단어의 첫 글자만 순서대로 이어 붙였고, 그다음 일부 글자를 l33tspeak 숫자로 바꿨을 수도 있다. 바꿀 수 있는 글자는 다음과 같다.

글자마다 따로 바꾸므로, 바꾼 글자의 모임은 어떤 부분집합이든 될 수 있다.

반지의 제왕 첫 문장 "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"을 보자. 각 단어의 첫 글자를 모으면 tbilcwhafiparmdmotcaaloth가 된다. $k$가 9 이상이었다면 비밀번호는 tbilcwh, 7b1lcwh4f, a, 4, 4al07h 가운데 하나일 수 있다.

아시시의 브라우저에는 비밀번호를 포함하는 문자열의 업로드를 막는 확장 프로그램이 설치되어 있다. 어느 글에서 비밀번호를 골랐는지 알아내려고, 아시시는 1초마다 새로운 글 하나의 "비밀번호 문자열"을 전송하라고 브라우저에 지시하는 웹페이지를 만들었다. 비밀번호 문자열이란 그 글에서 아시시가 고를 수 있었던 모든 비밀번호를 연속한 부분 문자열로 포함하는 문자열이다. 브라우저가 전송에 실패하는 순간, 아시시는 비밀번호를 어느 글에서 골랐는지 알게 된다.

예를 들어 $k = 2$이고 어떤 글의 단어 첫 글자가 google이라면 goo0og00gle9o909l3은 그 글의 비밀번호 문자열이다. 길이가 1 또는 2인 google의 모든 부분 문자열과 그 l33tspeak 변형이 전부 들어 있다.

어떤 글의 단어 첫 글자가 주어질 때, 그 글의 비밀번호 문자열이 가질 수 있는 가장 짧은 길이를 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 정수 $k$가 주어지고, 둘째 줄에 어떤 글의 단어 첫 글자를 공백 없이 이어 붙인 문자열 $S$가 주어진다.

제한:

• $1 \le T \le 20$
• $k = 2$
• $2k \le |S| \le 1000$
• $S$는 알파벳 소문자 a부터 z까지로만 이루어진다

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 $S$의 비밀번호 문자열이 가질 수 있는 가장 짧은 길이이다.

$k = 2$이고 $S =$ poppop일 때 길이가 가장 짧은 비밀번호 문자열의 예는 0ppop0이다. $k = 2$이고 $S =$ google일 때는 goo0og00gle9o909l3이 그런 예다.