import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

    static class Tree {
        Tree () {}

        Tree(String s) {
            this.s = s;
        }

        String s;
        List<Tree> neighbors = new ArrayList<Tree>();

        @Override
        public boolean equals(Object o) {
            return (o instanceof Tree) && ((Tree)o).s.equals(s);
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("DEBRUIJN.IN"));

        int N  = scanner.nextInt();

        for (int i = 0; i < N; i++) {
            int K = scanner.nextInt();
            String S = scanner.next();

            int len = S.length();

            Tree root;
            Tree current = new Tree();

            List<Tree> list = new ArrayList<Tree>();

            for (int j = 0; j < len-K+1; j++) {

                String sub = S.substring(j, j+K);
                //System.out.println(sub);
                if (j == 0) {
                    root = new Tree(sub);
                    current = root;
                } else {
                    Tree t = new Tree(sub);
                    current.neighbors.add(t);
                    current = t;
                }

                list.add(current);
            }

            List<Tree> fin = new ArrayList<Tree>();

            for (Tree tree : list) {
                if  (fin.contains(tree)) {
                    int idx = fin.indexOf(tree);
                    Tree fin_elem = fin.get(idx);
                    fin_elem.neighbors.addAll(tree.neighbors);
                } else {
                    fin.add(tree);
                }
            }

            int count = 0;

            for (Tree tree : fin) {
                if (tree.neighbors.size() > 1) {
                    count += 1;
                }
            }

            System.out.println(count);

        }
    }

}
