import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

/**
 * 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 int count = 0;

    static class Node {
        static Map<String, Node> nodes = new HashMap<String, A.Node>();
        Node () {}

        public static Node getNode(Node prev, String s)
        {
            Node cur;
            if (nodes.containsKey(s))
            {
                cur = nodes.get(s);
            }
            else
            {
                cur = new Node();
                nodes.put(s, cur);
            }
            if (prev != null)
            {
                prev.roads.add(cur);
            }
            return cur;
        }

        Set<Node> roads = new HashSet<Node>();
    }

    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++) {
            count = 0;
            Node.nodes = new HashMap<String, Node>();
            int K = scanner.nextInt();
            String S = scanner.next();

            int len = S.length();

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

                String sub = S.substring(j, j+K);
                //System.out.println(sub);

                node = Node.getNode(node, sub);
            }

            for (Node cur : Node.nodes.values()) {
                if (cur.roads.size()>1)
                {
                    count++;
                }
            }


            System.out.println(count);

        }
    }

}
