import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;


public class Main {

	/**
	 * @param args
	 * @throws FileNotFoundException
	 */
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new FileReader("DEBRUIJN.in"));
		int n = Integer.parseInt(in.readLine());
		
		for (int i = 0; i < n; i++) {
			int k=Integer.parseInt(in.readLine());
			if (k==1){System.out.println(0); continue;}
			String s = in.readLine();
			ArrayList al=new ArrayList();
			int mas[]=new int[256];
			int mas2[]=new int[256];
			for (int j = 0; j <= s.length() - k; j++) {
				
				String sub=s.substring(j,j+k);
				if(!al.contains(sub)){
					al.add(sub);
				}
				
				
			}
			Collections.sort(al);
			
			boolean t=false;
			for (int j = 0; j < al.size(); j++) {

						mas[al.get(j).toString().charAt(0)]++;
						mas2[al.get(j).toString().charAt(al.get(j).toString().length()-1)]++;
						
					
				
			}
			int sum=0;
			if(mas['A']>1)sum+=mas2['A'];
			if(mas['C']>1)sum+=mas2['C'];
			if(mas['G']>1)sum+=mas2['G'];
			if(mas['T']>1)sum+=mas2['T'];
			System.out.println(sum);
		}
		
	}

}
