import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: student
 * Date: 10.11.13
 * Time: 10:06
 * To change this template use File | Settings | File Templates.
 */
public class Main {
    public static void main(String[] args) throws Exception {
        solveA();
    }

//    static void solveC() throws Exception {
//        in = new BufferedReader(new FileReader(new File("FLOAT.IN")));
//        int t = F.nextInt();
//        for (int tt = 0 ; tt < t ; tt++) {
//            int p = F.nextInt(), q = F.nextInt();
//            println(q - p + 1);
//        }
//    }
    static int abs(int n, int k) { if (n < 0) n += k; return n % k == 0 ? k : n % k; }
    static void solveE() throws Exception {
        in = new BufferedReader(new FileReader(new File("HACK.IN")));
        int t = F.nextInt();
        for (int tt = 0 ; tt < t ; tt++) {
            int l = F.nextInt(), s = F.nextInt(), f = F.nextInt(), n = F.nextInt();
            int[] data = new int[n];

            for (int i = 0 ; i < n ; i++) {
                data[i] = F.nextInt();
            }

            List<Pair> A = new ArrayList<Pair>();
            int i1 = abs(data[0] + s, l), i2 = abs(s - data[0], l);

            if (i1 == i2) {
                Pair p = new Pair(i1, "D", 2);
                A.add(p);
            } else {
                Pair p1 = new Pair(abs(data[0] + s, l), "U");
                A.add(p1);

                Pair p2 = new Pair(abs(s - data[0], l), "D");
                A.add(p2);
            }

            for (int i = 1 ; i < n ; i++) {
                List<Pair> nextA = new ArrayList<Pair>();

                for (int j = 0 ; j < A.size() ; j++) {
                    Pair curr = A.get(j);

                    int nextU = abs(curr.x + data[i], l);
                    boolean exists = false;
                    for (Pair p : nextA) {
                        if (p.x == nextU) {
                            exists = true;
                            p.setMin(curr.min + "U");
                            p.count += curr.count;
                            break;
                        }
                    }
                    if (!exists) {
                        Pair p = new Pair(nextU, curr.min + "U", curr.count);
                        nextA.add(p);
                    }

                    int nextD = abs(curr.x - data[i], l);
                    exists = false;
                    for (Pair p : nextA) {
                        if (p.x == nextD) {
                            exists = true;
                            p.setMin(curr.min + "D");
                            p.count += curr.count;
                            break;
                        }
                    }
                    if (!exists) {
                        Pair p = new Pair(nextD, curr.min + "D", curr.count);
                        nextA.add(p);
                    }
                }

                //println(nextA);
                A = nextA;
            }

            long answer1 = 0;
            String answer = null;

            for (Pair p : A) {
                if (p.x == f) {
                    answer1 = p.count;
                    answer = p.min;
                    break;
                }
            }

            //println(A);
            if (answer == null) {
                println(0);
            } else {
                println(answer1 + " " + answer);
            }
        }
    }
    static void solveJ() throws Exception {
        in = new BufferedReader(new FileReader(new File("TOWER.IN")));
        int t = F.nextInt();

        for (int tt = 0 ; tt < t ; tt++) {
            int h = F.nextInt(), l = F.nextInt();
            List<Triple> A = new ArrayList<Triple>();

            for (int i = 0 ; i < h ; i++) {

                for (int j = 0 ; j < l ; j++) {
                    int curr = F.nextInt();
                    if (curr > -1) {
                        Triple tr = new Triple();
                        tr.x = curr;
                        tr.y = i;
                        tr.z = j;

                        A.add(tr);
                    }
                }
            }

            Collections.sort(A, new Comparator<Triple>() {
                public int compare(Triple o1, Triple o2) {
                    if (o1.x < o2.x) return -1;
                    else if (o1.x == o2.x) return 0;
                    else return 1;
                }
            });

            int result = 0;
            int[] state = new int[h];

            for (Triple curr : A) {
                int min = Math.min((curr.z - state[curr.y] + l) % l, (state[curr.y] - curr.z + l) % l);
                state[curr.y] = curr.z;
                result += 2 * 10 * curr.y + min * 5;
            }

            System.out.println(result);
        }
    }
    static void solveA() throws Exception {
        in = new BufferedReader(new FileReader(new File("DEBRUIJN.IN")));

        int tt = F.nextInt();
        for (int t = 0 ; t < tt ; t++) {
            int k = F.nextInt();
            String s = F.nextToken();

            List<String> l = new ArrayList<String>();
            for (int i = k; i < s.length() + 1; i++) {
                String curr = s.substring(i - k, i);
                l.add(curr);
            }

            Map<String, Map<String, Integer>> A = new TreeMap<String, Map<String, Integer>>();
            for (int i = 1 ; i < l.size() ; i++) {
                String curr = l.get(i), prev = l.get(i - 1);

                if (A.containsKey(prev)) {
                    A.get(prev).put(curr, 1);
                } else {
                    Map<String, Integer> m = new TreeMap<String, Integer>();
                    m.put(curr, 1);
                    A.put(prev, m);
                }
            }

            int result = 0;
            for (Map<String, Integer> x : A.values()) {
                int count = 0;
                for (Integer i : x.values()) {
                    if (i == 1) count++;
                }
                if (count > 1) result++;
            }

            //println(A);
            println(result);
        }
    }

    private static class Edge{
        int num, len;
        Edge(int x, int y) {num = x; len = y;}
    }

    static boolean mark[];
    static void solveI() throws Exception{
        int t;
        Scanner I = new Scanner(new File("SOCHI.IN"));
        t = I.nextInt();
        for (; t --> 0; ){
            int n, m;
            n = I.nextInt();
            m = I.nextInt();
            List<Edge> v[] = new ArrayList[n];
            for (int i = 0; i < n; i++)
                v[i] = new ArrayList<Edge>();
            int len[][] = new int[n][n];
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++)
                    len[i][j] = Integer.MAX_VALUE;
            }
            for (int i = 0; i < m; i++){
                int a, b, c;
                a = I.nextInt();
                b = I.nextInt();
                c = I.nextInt();
                a--;
                b--;
                if (len[a][b] > c){
                    v[a].add(new Edge(b, c));
                    len[a][b] = c;
                    len[b][a] = c;
                }
            }

            /*mark = new boolean[n];
            Arrays.fill(mark, false);
            int max = -1;
            for (int i = 0; i < n; i++){
                max = Math.max(goFrom(i, n, v), max);
            } */
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    /*for (int k = 0; k < v[j].size(); k++){
                        if (len[i][v[j].get(k).num] > len[i][j] + v[j].get(k).len)
                            len[i][v[j].get(k).num] = len[i][j] + v[j].get(k).len;
                    } */
                    for (int k = 0; k < n; k++){
                        if (len[j][i] != Integer.MAX_VALUE && len[i][k] != Integer.MAX_VALUE)
                            len[j][k] = Math.min(len[j][k], len[j][i] + len[i][k]);
                    }
                }
            }
            int max = 0;
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    if (len[i][j] != Integer.MAX_VALUE && i != j)
                        max = Math.max(len[i][j], max);
                }
            }
            System.out.println(max);
        }
    }
    /*static int goFrom(int from, int n, List<Edge>[] v){
        if (mark[from])
            return -1;
        else{
            mark[from] = true;
            int len[][] = new int[n][n];
            for (int i = 0; i < n; i++)
                Arrays.fill(len[i], Integer.MAX_VALUE);
            len[0][from] = 0;
            for (int y = 0; y < 1;){
                for (int i = 0; i < n; i++){
                    for (int j = 0; j < v[i].size(); j++){
                        if (len[i+1][j] > len[i][v[i].get(j).num] + )
                    }
                }
            }
        }
    }              */
    static class Pair {
        int x;
        String min;
        public Pair(int x, String min) {
            this.x = x;
            this.min = min;
        }
        public Pair(int x, String min, long count) {
            this.x = x;
            this.min = min;
            this.count = count;
        }
        long count = 1;
        public String toString() {return x + " " + min + " " + count;}
        public void setMin(String s) {
            if (s.compareTo(min) < 0 || min == null) min = s;
        }
    }
    static class Triple {
        int x, y, z;
        public String toString() {return x + " " + y + " " + z;}
    }
    static void println(Object o) {
        System.out.println(o);
    }
    static BufferedReader in;
    static class F {
        static StringTokenizer st;
        static String nextToken() throws Exception {
            if (st == null || !st.hasMoreTokens()) st = new StringTokenizer(in.readLine());
            return st.nextToken();
        }
        static Integer nextInt() throws Exception {
            return Integer.parseInt(nextToken());
        }
    }
}
