// package LeetCode;

import java.util.*;
import java.io.*;

public class Main {

	static class Reader {
		BufferedReader br;
		StringTokenizer st;

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

		public int nextInt() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Integer.parseInt(st.nextToken());
		}

		public float nextFloat() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Float.parseFloat(st.nextToken());
		}

		public long nextLong() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Long.parseLong(st.nextToken());
		}

		public double nextDouble() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return Double.parseDouble(st.nextToken());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(br.readLine());
			}
			return st.nextToken();
		}
	}

	static class Pair implements Comparable<Pair> {
		int index, val;

		public Pair(int index, int val) {
			this.index = index;
			this.val = val;
		}

		@Override
		public int compareTo(Pair o) {
			return o.val - this.val;
		}
	}

	static int mod = (int) (1e9 + 7);

	public static void main(String[] args) throws IOException {
		Reader sc = new Reader();
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		try {
			int t = sc.nextInt();
			while (t-- > 0) {
				int n = sc.nextInt();
				char[] arr = sc.next().toCharArray();
				int[][] count = new int[26][n];
				for (int i = 0; i < n; i++) {
					count[arr[i] - 'a'][i]++;
				}
				if(n==1) {
					if(arr[0]=='a')
						out.println(0);
					else
						out.println(1);
					continue;
				}
				for (int i = 0; i < 26; i++) {
					for (int j = 1; j < n; j++) {
//						System.out.println(i+" "+j);
						count[i][j] += count[i][j - 1];
					}
				}
				int start = 0, end = n - 1;
				long ans = 0;
				int curr = 0;
				while (start < end) {
					int mid = (end - start) / 2 + start;
					int left = count[curr][mid] - (start > 0 ? count[curr][start - 1] : 0);
					int right = count[curr][end] - count[curr][mid];
					if(end-start+1==2) {
						if (left > right) {
							ans+=(arr[end]==('a'+curr+1)?0:1);
						} else if(right>left){
							ans+=(arr[start]==('a'+curr+1)?0:1);
						} else {
							if(arr[start]=='a'+curr+1 || arr[end]=='a'+curr+1) {
								ans+=1;
							} else {
								if(left==0)
									ans+=2;
								else
									ans+=1;
							}
						}
						break;
					}
					if (left > right) {
						ans = ans + (mid - start + 1) - left;
						start = mid + 1;
					} else if(right>left){
						ans = ans + (end - mid) - right;
						end = mid;
					} else {
						curr++;
						int mid1 = (mid-start)/2 + start;
//						System.out.println(mid1);
						int left1 = count[curr][mid1] - (start > 0 ? count[curr][start - 1] : 0);
						int right1 = count[curr][mid] - count[curr][mid1];
						
						mid1 = (end-(mid+1))/2 + (mid+1);
//						System.out.println(mid1);
						int left2 = count[curr][mid1] - ((mid+1) > 0 ? count[curr][mid] : 0);
						int right2 = count[curr][end] - count[curr][mid1];
						int max1 = Math.max(left1, right1);
						int max2 = Math.max(left2, right2);
						if(max1>max2) {
							end = mid;
							ans = ans + (end - mid) - right;
						} else {
							ans = ans + (mid - start + 1) - left;
							start = mid + 1;
						}
						curr--;
						
					}
					curr++;
				}
				out.println(ans);
			}
			out.flush();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
//6
//4
//0 0 1 2
//4
//1 1 2 4
//4
//0 1 3 3
//4
//1 1 3 4
//4
//0 2 2 3
//4
//1 2 2 2

//3 3 0 1 
//-1
//-1
//-1
//1 0 4 2 
//0 1 1 3 
