PermRLE

당신은 실행 길이 부호화(RLE) 압축 알고리즘을 약간 변형한 PermRLE을 고안했다.

문자열을 압축하기 위해, 이 알고리즘은 1부터 k까지의 정수에 대한 어떤 순열을 선택하고, 주어진 문자열의 처음 k개 문자에 이 순열을 적용한 다음, 이어지는 k개 문자의 블록에 적용하는 식으로 계속한다. 문자열의 길이는 k로 나누어떨어져야 한다. 모든 블록을 순열에 따라 재배치한 후, 새 문자열을 뒤에서 설명하는 RLE을 사용하여 압축한다.

주어진 순열 p를 k개 문자의 블록에 적용한다는 것은 이 문자들 중 p[1]-번째 문자를 첫 번째 위치에 놓고, 이어서 p[2]-번째 문자를 두 번째 위치에 놓는 식으로 계속하는 것을 의미한다. 예를 들어, 순열 {3,1,4,2}을 블록 "abcd"에 적용하면 "cadb"가 된다. 이를 더 긴 문자열 "abcdefghijkl"에 블록 단위로 적용하면 "cadbgehfkilj"가 된다.

그런 다음 순열에 따라 재배치된 문자열을 실행 길이 부호화를 사용하여 압축한다. 단순화를 위해, 문자열의 압축 크기를 연속해서 나오는 같은 문자로 이루어진 그룹의 수로 간주한다. 예를 들어, "aabcaaaa"의 압축 크기는 4이다. 네 그룹 중 첫 번째 그룹은 문자 "a" 두 개로 이루어진 그룹이고, 그다음에는 각각 문자 하나만 포함하는 두 그룹 "b"와 "c"가 있으며, 마지막에는 문자 "a"로 이루어진 더 긴 그룹이 있다.

물론 압축 크기는 선택한 순열에 따라 달라질 수 있다. 압축 알고리즘의 목표는 압축된 텍스트의 크기를 최소화하는 것이므로, 가능한 가장 작은 압축 크기를 만드는 순열을 선택하고 그 크기를 출력해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. N = 20 S에는 소문자 'a'부터 'z'까지만 포함된다 S의 길이는 k로 나누어떨어진다

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ k ≤ 5 1 ≤ S의 길이 ≤ 1000

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ k ≤ 16 1 ≤ S의 길이 ≤ 50000

입력의 첫 번째 줄에는 케이스의 수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 케이스의 첫 번째 줄에는 k가 주어진다. 두 번째 줄에는 압축할 문자열 S가 주어진다.

각 테스트 케이스마다 "Case #X: Y"를 포함하는 한 줄을 출력해야 한다(따옴표는 명확성을 위한 것이다). 여기서 X는 테스트 케이스 번호이고 Y는 S의 최소 압축 크기이다.