

        import java.lang.reflect.Array;
		import java.util.*;
		import java.io.*;
		 public class Main {
		    public static void main ( String args[] ) {
                FastReader sc = new FastReader();
                PrintWriter out = new PrintWriter(System.out);
                int t= sc.nextInt();
                while(t-->0){
                	int n = sc.nextInt();
                	String s = sc.next() ;
                	if (s.length()==1)
                		System.out.println(s.equals("a")?0:1 );
                	else {
                	StringBuilder s1 = new StringBuilder(), s2 = new StringBuilder() , s3 = new StringBuilder() , s4 = new StringBuilder(),
					 s5 = new StringBuilder(), s6 = new StringBuilder() , s7 = new StringBuilder() , s8 = new StringBuilder();

					for (int i = 0 ; i < n/2 ;i++){
                		s1.append('a');
                		s2.append('a');
                		s3.append('a');
                		s4.append('a');
					}
					for (int i = n/2 ; i<(n/2+n/4) ; i++){
						s3.append('b');
						s4.append('b');
					}
					for (int i = (n/2+n/4) ; i<(n/2+n/4+n/8) ; i++){
						s3.append('d');
						s4.append('c');
					}
					for (int i = (n/2+n/4+n/8) ; i<n ; i++){
						s3.append('c');
						s4.append('d');
					}

                	for (int i = n/2 ; i < (n/2+n/8) ; i++){
                		s1.append('d');
                		s2.append('c');
					}
					for (int i = (n/2+n/8)  ; i < (n/2+n/8+n/8) ; i++){
						s1.append('c');
						s2.append('d');
					}
					for (int i = (n/2+n/8+n/8) ; i < n ; i++){
						s1.append('b');
						s2.append('b');
					}




						int count1 = 0 ;
					int count2 = 0 ;	int count3 = 0 ;	int count4 = 0 ;
					int count5 = 0 ;
					int count6 = 0 ;	int count7 = 0 ;	int count8 = 0 ;

int count = (int)1e9 ;
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s1.charAt(i))
							count1++;
					}
					count = Math.min(count,count1 );
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s2.charAt(i))
							count2++;
					}
					count = Math.min(count,count2 );
					if (n>2){
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s3.charAt(i))
							count3++;
					}
					count = Math.min(count,count3 );
					if (n>4){
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s4.charAt(i))
							count4++;
					}

					count = Math.min(count,count4 );}}
					s5 = s1.reverse();
					s6= s2.reverse();
					s7 = s3.reverse();
					s8 = s4.reverse();

					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s5.charAt(i))
							count5++;
					}
					count = Math.min(count,count5 );
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s6.charAt(i))
							count6++;
					}
					count = Math.min(count,count6 );
					if(n>2){
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s7.charAt(i))
							count7++;
					}
					count = Math.min(count,count7 );
					if (n>4){
					for (int i = 0 ; i < n ; i++){
						if (s.charAt(i)!=s8.charAt(i))
							count8++;
					}
					count = Math.min(count,count8);}}
					System.out.println(count);}


				}






                }

		    static int [] freq (int [] a ) {
		    	int max = 0 ;
		    	for (int i =0 ; i < a.length ; i++) {
		    		max = Math.max(a[i], max);

		    	}
		    	int [] b = new int [max+1];
		    	for (int i = 0 ; i < a.length ; i++) {
		    		b[a[i]]++;

		    	}
		    	return b ;

		    }
		     static class Graph
		    {
		        private int V;   // No. of vertices

		        // Array  of lists for Adjacency List Representation
		        private TreeSet<Integer> adj[];

		        // Constructor
		        Graph(int v)
		        {
		            V = v;
		            adj = new TreeSet[v];
		            for (int i=0; i<v; ++i)
		                adj[i] = new TreeSet<Integer>();
		        }

		        //Function to add an edge into the graph
		        void addEdge(int v, int w)
		        {
		            adj[v].add(w);  // Add w to v's list.
		        }

		        // A function used by DFS
		      /*  void DFSUtil(int v,boolean visited[])
		        {
		            // Mark the current node as visited and print it
		            visited[v] = true;
		            System.out.print(v+" ");

		            // Recur for all the vertices adjacent to this vertex
		            Iterator<Integer> i = adj[v].listIterator();
		            while (i.hasNext())
		            {
		                int n = i.next();
		                if (!visited[n])
		                    DFSUtil(n, visited);
		            }
		        }

		        // The function to do DFS traversal. It uses recursive DFSUtil()
		        void DFS(int v)
		        {
		            // Mark all the vertices as not visited(set as
		            // false by default in java)
		            boolean visited[] = new boolean[V];

		            // Call the recursive helper function to print DFS traversal
		            DFSUtil(v, visited);
		        }
		    }*/}
		    public static long sum (long mid, long k ) {
		    	long sum1 = (mid-1)*(mid) /2 ;
		    	long sum2 = (k)*(k+1) /2 ;
		    	return sum2-sum1 ;


		    }
		    public static void swap(Long []a ,int i , int j ) {
		    	long temp = a[i];
		    	a[i]= a[j];
		    	a[j]= temp ;

		    }

		    static class FastReader
			{
				BufferedReader br;
				StringTokenizer st;

				public FastReader()
				{
					br = new BufferedReader(new
							InputStreamReader(System.in));
				}

				String next()
				{
					while (st == null || !st.hasMoreElements())
					{
						try
						{
							st = new StringTokenizer(br.readLine());
						}
						catch (IOException  e)
						{
							e.printStackTrace();
						}
					}
					return st.nextToken();
				}

				int nextInt()
				{
					return Integer.parseInt(next());
				}

				long nextLong()
				{
					return Long.parseLong(next());
				}

				double nextDouble()
				{
					return Double.parseDouble(next());
				}

				String nextLine()
				{
					String str = "";
					try
					{
						str = br.readLine();
					}
					catch (IOException e)
					{
						e.printStackTrace();
					}
					return str;
				}
		}
		 }
		  class Pair {
			int x ;
			int y ;
			public Pair(int x ,int y){
				this.x = x;
				this.y=y;}
		}

		  class Pair1 implements Comparable{
			int x ;
			int y ;
			public Pair1(int x ,int y){
				this.x = x;
				this.y=y;}
			public int compareTo(Object o) {
				Pair1 a = (Pair1) o ;

				return (a.x-this.x);
			}

			}
		 class Pair2 implements Comparable{
			int x ;
			int y ;
			public Pair2(int x ,int y){
				this.x = x;
				this.y=y;}
			public int compareTo(Object o) {
				Pair2 a = (Pair2) o ;

				return (this.y-a.y);
			}
		 }
		 