import java.util.*;
public class Main
{
    public static int good_string(String str, char s, boolean res){
        
        int len = str.length();
        int count1 = 0;
        int count2 = 0;
        for(int i = 0; i<len/2; i++){
            if(str.charAt(i)==s) count1++;
        }
        for(int i = len/2; i<len; i++){
            if(str.charAt(i)==s) count2++;
        }
        if(count1==len/2 || count2==len/2) res = true;
        else res = false;
        return Math.min(len/2-count1, len/2-count2);
    }
    
    public static int good(String str){
        int n = str.length();
        boolean res = true;
        int k = good_string(str,'a', res);
        if(res){
		    String str1 = str.substring(0,n/2);
		    String str2 = str.substring(n/2, n);
		    boolean res1 = true;
		    boolean res2 = true;
		    int k1 = good_string(str1,'b',res1);
		    int k2 = good_string(str2,'b', res2);
	        if(res1 || res2){
	            k+=Math.min(k1,k2);
	        }
		}
		return k;
    }
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0){
		    int n = sc.nextInt();
		    String str = sc.next();
		    if(str.length()==1){
		        if(str.equals("a")){
		            System.out.println(0);
		        }
		        else System.out.println(1);
		        return;
		    }
		    System.out.println(good(str));
    	}
	}
}