잃어버린 비밀번호 (라지)
시간 제한100초메모리 제한512 MB
문자열 S와 정수 k가 주어질 때 길이가 1부터 k까지인 S의 모든 부분 문자열에 대한 l33tspeak 변형을 부분 문자열로 담은 가장 짧은 문자열의 길이를 구합니다.
문제
아시시는 비밀번호를 잊어버렸다. 만드는 방법만 기억한다. 어떤 글에서 연속한 단어를 최대 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'까지의 소문자로만 이루어진다.
제한
- S의 길이는 이상 5000 이하이다.
- 길이가 이하인 비밀번호 문자열이 항상 존재한다.
출력
각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 S에 대응하는 비밀번호 문자열의 최소 길이다.
힌트
k = 2, S = "poppop"일 때 "0ppop0"은 비밀번호 문자열이다.
k = 2, S = "google"일 때 "goo0og00gle9o909l3"은 비밀번호 문자열이다.