K-좋음 문자열

Charles는 문자열의 좋음 점수를 $1 \le i \le \mathbf{N}/2$인 인덱스 $i$ 중 $\mathbf{S}_i\ne\mathbf{S}_{\mathbf{N}-i+1}$를 만족하는 인덱스의 수로 정의한다($1$부터 인덱싱). 예를 들어, 문자열 CABABC의 좋음 점수는 $2$이다. 이는 $\mathbf{S}_2 \ne \mathbf{S}_5$이고 $\mathbf{S}_3 \ne \mathbf{S}_4$이기 때문이다.

Charles는 Ada에게 대문자로 구성된 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$을 주고, 이를 좋음 점수가 $\mathbf{K}$인 문자열로 바꾸라고 요청했다. 한 번의 연산으로 Ada는 문자열의 임의의 문자를 임의의 대문자로 바꿀 수 있다. 주어진 문자열을 좋음 점수가 $\mathbf{K}$와 같은 문자열로 변환하는 데 필요한 최소 연산 횟수를 Ada가 구하도록 도와줄 수 있는가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $0 \le \mathbf{K} \le \mathbf{N}/2$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 100$.

테스트 세트 2

시간 제한: 40초. 최대 $10$개의 테스트 케이스에 대해 $1 \le \mathbf{N} \le 2 \times 10^5$이다. 나머지 케이스에 대해서는 $1 \le \mathbf{N} \le 100$이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$과 $\mathbf{K}$가 주어진다. 각 테스트 케이스의 두 번째 줄에는 대문자로 구성된 길이 $\mathbf{N}$의 문자열 $\mathbf{S}$가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 주어진 문자열 $\mathbf{S}$을 좋음 점수가 $\mathbf{K}$와 같은 문자열로 변환하는 데 필요한 최소 연산 횟수이다.

예제 케이스 #1에서 주어진 문자열의 좋음 점수는 이미 $1$이다. 따라서 필요한 최소 연산 횟수는 $0$이다.

예제 케이스 #2에서 한 가지 방법은 좋음 점수가 $2$이 되도록 인덱스 $1$의 문자를 B로 바꾸는 것이다. 따라서 필요한 최소 연산 횟수는 $1$이다.