import java.util.Scanner;

public class HihoCoder1052 {

	static char[] item = { 'A', 'C', 'G', 'T' };

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int num = in.nextInt();
		while (num > 0) {
			num--;
			String value = in.next();
			int index = in.nextInt();
			handle(value, index);
		}
	}

	/**ɻ n-k ѭ
	 * @param value
	 * @param k
	 */
	private static void handle(String value, int k) {
		int n = value.length();
		char[] s = value.toCharArray();
		int ans =0 ;
		for (int i = 0; i <= n - k - 1; i++) {
			int[] word = new int[26];
			int p = i; 
 while (p < n) 
 { 
 word[s[p] - 'A']++; 
 p = p + n - k; 
 } 
 int sum = 0; 
 int max_sum = 0; 
 for (int j = 0; j < 4; j++) 
 { 
 sum += word[item[j] - 'A']; 
 if (max_sum < word[item[j] - 'A']) 
 max_sum = word[item[j] - 'A']; 
 } 
 ans += sum - max_sum; 
		}
		System.out.println(ans);

	}

}