16425 | 복사 및 붙여넣기

소문자 영문자로만 이루어진 특정 목표 문자열 S를 만들려고 한다. 빈 문자열로 시작하며, 다음 연산을 수행할 수 있다.

임의의 소문자 영문자 하나를 문자열 끝에 추가한다.
문자열의 임의의 부분 문자열(즉, 문자열의 어떤 시작 지점과 어떤 끝 지점 사이에 있는 모든 문자)을 클립보드에 복사한다. 이 연산을 수행하면 이전에 클립보드에 있던 내용은 덮어쓰인다. 클립보드는 처음에 비어 있다.
클립보드의 전체 내용을 문자열 끝에 추가한다. (클립보드의 내용은 바뀌지 않는다.)

목표 문자열을 만드는 데 필요한 최소 연산 횟수는 얼마인가? 추가 문자가 전혀 없이 목표 문자열을 정확히 만들어야 한다는 점에 유의한다.

시간 제한: 테스트 세트당 40초. 메모리 제한: 1GB. S는 a부터 z까지의 범위에 있는 소문자 영문자로만 이루어진다.

1 ≤ T ≤ 100. 1 ≤ S의 길이 ≤ 6.

1 ≤ T ≤ 100. 1 ≤ S의 길이 ≤ 300.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 목표 문자열 S가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 목표 문자열을 만드는 데 필요한 최소 연산 횟수(문제 설명에 기술된 연산 기준)이다.

3
abcabab
aaaaaaaaaaa
vnsdmvnsnsdmkvdmkvnsdmk

Case #1: 6
Case #2: 7
Case #3: 15

예제 케이스 #1의 최적해는 다음과 같다.

예제 케이스 #2의 최적해는 다음과 같다.