PermRLE (큰 입력)

실행 길이 부호화(run-length encoding, RLE)를 조금 고친 압축 알고리즘 PermRLE를 만들었다.

이 알고리즘은 문자열을 압축할 때 먼저 1부터 $k$까지의 정수로 이루어진 순열 하나를 고른다. 그 순열을 문자열의 앞 $k$글자에 적용하고, 다음 $k$글자 묶음에 다시 적용하고, 이런 식으로 문자열 끝까지 반복한다. 문자열의 길이는 $k$의 배수다. 모든 묶음을 재배열한 다음, 새로 만들어진 문자열을 RLE로 압축한다.

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

재배열한 문자열은 RLE로 압축한다. 여기서는 압축 크기를 같은 글자가 연속으로 이어진 덩어리의 개수로 정의한다. 예를 들어 "aabcaaaa"의 압축 크기는 4다. 'a'가 두 개 이어진 덩어리, 'b' 하나로 이루어진 덩어리, 'c' 하나로 이루어진 덩어리, 마지막으로 'a'가 네 개 이어진 덩어리로 나뉜다.

압축 크기는 고른 순열에 따라 달라진다. 압축 크기가 가장 작아지는 순열을 골라, 그때의 압축 크기를 출력하라.

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

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

제한

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

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