Problem

Charles defines the goodness score of a string as the number of indices i such that S_i ≠ S_n-i+1 where 1 ≤ i ≤ N/2 (1-indexed). For example, the string CABABC has a goodness score of 2 since S₂ ≠ S₅ and S₃ ≠ S₄.

Charles gave Ada a string S of length N, consisting of uppercase letters and asked her to convert it into a string with a goodness score of K. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to K?

Limits

Memory limit: 1 GB.
1 ≤ T ≤ 100.
0 ≤ K ≤ N/2.

Test Set 1

Time limit: 20 seconds.
1 ≤ N ≤ 100.

Test Set 2

Time limit: 40 seconds.
1 ≤ N ≤ 2×10⁵ for at most 10 test cases.
For the remaining cases, 1 ≤ N ≤ 100.