K-굿니스 문자열

Charles는 문자열의 굿니스 점수를 $1 \le i \le N/2$인 모든 $i$ 중 $S_i \ne S_{N-i+1}$인 $i$의 개수로 정의한다(1-indexed). 예를 들어 문자열 CABABC는 $S_2 \ne S_5$이고 $S_3 \ne S_4$이므로 굿니스 점수가 2이다.

Charles는 Ada에게 대문자로만 이루어진 길이 $N$의 문자열 $S$를 주고, 굿니스 점수가 $K$인 문자열로 바꾸라고 했다. 한 번의 연산으로 Ada는 문자열의 임의의 문자를 임의의 대문자로 바꿀 수 있다. 주어진 문자열을 굿니스 점수가 $K$인 문자열로 바꾸는 데 필요한 최소 연산 횟수를 구하시오.

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

각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $K$가 주어진다. 둘째 줄에는 대문자로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 주어진 문자열 $S$를 굿니스 점수가 $K$인 문자열로 바꾸는 데 필요한 최소 연산 횟수이다.

• $1 \le T \le 100$.
• $0 \le K \le N/2$.

예제 1에서는 주어진 문자열의 굿니스 점수가 이미 1이다. 따라서 필요한 최소 연산 횟수는 0이다.

예제 2에서는 굿니스 점수를 2로 만들기 위해 인덱스 1의 문자를 B로 바꾸는 방법이 있다. 따라서 필요한 최소 연산 횟수는 1이다.