#include <set>
#include <map>
#include <list>
#include <deque>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <utility>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;

struct Suffix
{
	int h[2];
	int index;
};

bool operator < (const Suffix & a, const Suffix & b)
{
	if(a.h[0] != b.h[0])
		return a.h[0] < b.h[0];
	return a.h[1] < b.h[1];
}

bool Equivalent(const Suffix & a, const Suffix & b)
{
	return a.h[0] == b.h[0] && a.h[1] == b.h[1];
}

const int ALPHA_SZ = 1 << 8;
const int MAX_PW = 18;
const int MAX_SZ = 1 << MAX_PW;

int n;
int pw2 = 1;
char str[MAX_SZ];
int cnt[ALPHA_SZ];
int order[MAX_SZ];
Suffix suff[MAX_SZ];
int pos[MAX_PW][MAX_SZ];

void BuildArray()
{
	memset(cnt, 0, ALPHA_SZ * sizeof(int));
	for(int i = 0; i < n; i++)
	{
		cnt[str[i]] = 1;
	}
	for(int i = 1; i < ALPHA_SZ; i++)
	{
		cnt[i] += cnt[i - 1];
	}	
	for(int i = 0; i < n; i++)
	{
		pos[0][i] = cnt[str[i]] - 1;		
	}

	pw2 = 1;
	for(; (1 << (pw2 - 1)) < n; pw2++)
	{
		int length2 = 1 << (pw2 - 1);
		for(int i = 0; i < n; i++)
		{
			suff[i].index = i;
			suff[i].h[0] = pos[pw2 - 1][i];
			suff[i].h[1] = i + length2 < n ? pos[pw2 - 1][i + length2] : -1;
		}

		sort(suff, suff + n);
		pos[pw2][suff[0].index] = 0;
		for(int i = 1; i < n; i++)
		{
			int nowSuffix = suff[i].index;
			int prevSuffix = suff[i - 1].index;
			if(Equivalent(suff[i], suff[i - 1]))
			{
				pos[pw2][nowSuffix] = pos[pw2][prevSuffix];
			}
			else
			{
				pos[pw2][nowSuffix] = pos[pw2][prevSuffix] + 1;
			}
		}
	}
	pw2--;

	for(int i = 0; i < n; i++)
	{
		order[pos[pw2][i]] = i;
	}
}

int LCP(int a, int b)
{
	int ret = 0;

	for(int pw = pw2; pw >= 0 && a < n && b < n; pw--)
	{
		if(pos[pw][a] == pos[pw][b])
		{
			ret += 1 << pw;
			a += 1 << pw;
			b += 1 << pw;
		}
	}

	return ret;
}

//This code is intended for testing only and is not a part of the solution

std::vector<int> SuffixArrayBruteForce()
{
	std::vector<std::string> suffix(n);
	std::vector<int> ret(n);
	for(int i = 0; i < n; i++)
	{
		suffix[i].assign(str + i, str + n);
	}

	std::sort(suffix.begin(), suffix.end());
	for(int i = 0; i < n; i++)
	{
		ret[i] = n - suffix[i].length();
	}

	return ret;
}

int LCPBruteForce(const std::vector<int> & sa, int a, int b)
{
	int i = 0;
	for(; a + i < n && b + i < n && str[a + i] == str[b + i]; i++);
	return i;
}

void Test(int testNumber)
{
	srand(time(0));
	const char alphabet[] = "ACGT";
	for(int test = 0; test < testNumber; test++)
	{
		n = 1000 + rand() % 10000;
		for(int i = 0; i < n; i++)
		{
			str[i] = alphabet[rand() % 4];
		}

		BuildArray();
		std::vector<int> sa = SuffixArrayBruteForce();
		for(int i = 0; i < n; i++)
		{
			assert(order[i] == sa[i]);
			assert(i == 0 || LCP(order[i], order[i - 1]) == LCPBruteForce(sa, sa[i], sa[i - 1]));
		}

		std::cerr << "Test #" << test << ": PASSED" << std::endl;
	}
}


int main()
{
#ifdef _TEST_
	Test(100);
#endif

	int k;
	int tests;
	std::string alphabet = "ACGT";
	std::ifstream in("DEBRUIJN.IN");	
	for(in >> tests; tests--; )
	{
		int answer = 0;
		in >> k >> str;		
		n = strlen(str);
		try
		{
			if(n > 100000)
			{
				throw "THE OUTPUT IS TOO LARGE";
			}

			for(int i = 0; i < n; i++)
			{
				if(alphabet.find(str[i]) == alphabet.npos)
				{
					throw "GARBAGE IN THE INPUT";
				}
			}
		}
		catch(const char * msg)
		{
			std::cerr << msg;
			abort();
		}

		BuildArray();		
		for(int i = 0; i < n; )
		{
			int j = i + 1;
			if(order[i] + k < n)
			{
				std::string symbol(1, str[order[i] + k]);
				for(; j < n && LCP(order[j], order[j - 1]) >= k; j++)
				{
					if(order[j] + k < n)
					{
						symbol += str[order[j] + k];
					}
				}

				std::sort(symbol.begin(), symbol.end());
				symbol.erase(std::unique(symbol.begin(), symbol.end()), symbol.end());
				if(symbol.size() > 1)
				{
					answer++;
				}
			}

			i = j;
		}

		std::cout << answer << std::endl;		
	}

	std::cerr << clock() << std::endl;
	return 0;
}