import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * User: student
 * Date: 10.11.13
 * Time: 11:57
 * To change this template use File | Settings | File Templates.
 */
public class JavaA {

    //   public static class Node {}

    public static void main(String[] args) throws Throwable {
        BufferedReader reader = new BufferedReader(new FileReader("DEBRUIJN.IN"));
        int tests = Integer.valueOf(reader.readLine()).intValue();

        Map<String, Set<String>> map = new HashMap<String, Set<String>>();
        for (int ii = 0; ii < tests; ++ii) {
            map.clear();

            int k = Integer.valueOf(reader.readLine()).intValue();
            String line = reader.readLine();
            String last = null;
            int answer = 0;
            for (int i = 0; i <= line.length() - k; ++i) {
                String sub = line.substring(i, i + k);
                if (!map.containsKey(sub))
                    map.put(sub, new HashSet<String>());
                if (last != null)
                    map.get(last).add(sub);
                last = sub;
            }

            for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
               // System.out.println(entry.getKey() + " -> " + entry.getValue());
                if (entry.getValue().size() > 1) answer++;
            }
            System.out.println(answer);
        }
    }
}