PermRLE (작은 입력)

RLE(런 길이 인코딩) 압축을 약간 변형한 PermRLE 알고리즘을 만들었다.

문자열을 압축할 때 이 알고리즘은 1부터 $k$까지의 정수로 이루어진 순열 하나를 고른다. 그리고 그 순열을 문자열의 처음 $k$글자에 적용하고, 다음 $k$글자 블록에 적용하고, 같은 방식으로 마지막 블록까지 적용한다. 문자열의 길이는 $k$의 배수여야 한다. 모든 블록을 재배열한 다음, 새로 만들어진 문자열을 아래에서 설명하는 RLE로 압축한다.

순열 $p$를 $k$글자 블록에 적용한다는 말은, 그 블록의 $p[1]$번째 글자를 첫 번째 자리에 놓고, $p[2]$번째 글자를 두 번째 자리에 놓고, 이런 식으로 $k$번째 자리까지 채운다는 뜻이다. 예를 들어 순열 $\{3, 1, 4, 2\}$를 블록 abcd에 적용하면 cadb가 된다. 같은 순열을 더 긴 문자열 abcdefghijkl에 블록 단위로 적용하면 cadbgehfkilj가 된다.

재배열이 끝난 문자열은 런 길이 인코딩으로 압축한다. 문제를 간단히 하기 위해, 문자열의 압축 크기를 같은 글자가 연속으로 이어지는 그룹의 개수로 정의한다. 예를 들어 aabcaaaa의 압축 크기는 4이다. 네 그룹 중 첫 번째는 a 두 개로 이루어진 그룹이고, 그다음은 각각 한 글자뿐인 b 그룹과 c 그룹이며, 마지막은 a 네 개로 이루어진 더 긴 그룹이다.

압축 크기는 어떤 순열을 고르는지에 따라 달라진다. 압축 알고리즘의 목표는 압축된 텍스트의 크기를 최소로 만드는 것이므로, 압축 크기가 가장 작아지는 순열을 골라 그때의 압축 크기를 출력하면 된다.

첫 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다.

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

제한

• $1 \le N \le 20$
• $S$는 알파벳 소문자 a부터 z까지만 포함한다.
• $S$의 길이는 $k$의 배수이다.
• $2 \le k \le 5$
• $1 \le |S| \le 1000$

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄을 출력한다. $X$는 테스트 케이스의 번호이고, $Y$는 $S$의 최소 압축 크기이다.