import sun.security.util.BigInt;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * User: student
 * Date: 29.05.11
 * Time: 14:47
 * To change this template use File | Settings | File Templates.
 */
public class shadoof {
    public static void main(String []args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("DEBRUIJN.IN"));
        Integer n=Integer.parseInt(reader.readLine().toString());
        String s;
        int k=0;
        ArrayList<StringBuilder> Edges;
        int []arr=new int[0];
        while(k<n){
        while((s=reader.readLine())!=null){
                  Integer lenght=Integer.parseInt(s);
                  Edges=new ArrayList<StringBuilder>();
                  StringBuilder  data= new StringBuilder(reader.readLine());
                  for(int i=0;i<data.length()-lenght;i++){
                      StringBuilder sub=new StringBuilder(data.substring(i,i+lenght));
                      Edges.add(sub);
                     arr= new int[Edges.size()];
                      for(int e=0;e<arr.length-1;e++)
                          arr[e]=1;
                      int counterRaz=0;
                      Iterator iterator=Edges.iterator();
                      while(iterator.hasNext()){
                          StringBuilder s1= (StringBuilder) iterator.next();
                          int t=0;

                          for(int l=Edges.indexOf(s1);l<Edges.size();l++){
                               if(s1.charAt(0)==Edges.get(l).charAt(1)
                                       && l!=Edges.indexOf(s1)
                                       && Math.abs(l-Edges.indexOf(s1))>1)
                              {
                                  arr[t]++;
                                  }
                              t++;
                          }
                      }

                  }
            int sum=0;
            for(int l=0;l<arr.length;l++)
                if(arr[l]>1)
                sum++;

            System.out.println(sum);


            //System.out.println(count);
        }
        k++;
        }
    }
}
