#include<bits/stdc++.h>
#include <tuple>

using namespace std;

using ll = long long;

vector<int>z_algorithm(string &s) {
	int n = s.size();
	vector<int>z(n);
	z[0] = n;
	int i = 1, j = 0;
	while(i<n) {
		while(i+j<n and s[i+j]==s[j]) ++j;
		z[i] = j;
		if(j==0) {
			++i;
			continue;
		}
		int k = 1;
		while(i+k<n and k+z[k]<j) z[i+k]=z[k], ++k;
		i += k, j -= k;
	}
	return z;
}

void enum_run_rec(int l, int r, string &s, vector<tuple<int, int, int>>&runs) {
	if(r-l<=1) return;
	int m = (l+r)/2;
	enum_run_rec(l, m, s, runs);
	enum_run_rec(m, r, s, runs);

	auto f = [&](bool rev) {
		string t = s.substr(l, r-l);
		if(rev) {
			reverse(begin(t), end(t));
			m = l + r - m;
		}

		int len = r-l, mid = m-l;
		string tl = t.substr(0, mid);
		reverse(begin(tl), end(tl));
		string tr = t.substr(mid, len-mid) + t;
		auto zl = z_algorithm(tl), zr = z_algorithm(tr);
		zl.push_back(0);

		for(int k = 1 ; mid-k>=0 ; ++k) {
			int li = m-k-zl[k], ri = m+min(r-m, zr[len-k]);
			if(rev) {
				swap(li, ri);
				li = l+r-li;
				ri = l+r-ri;
			}
			if(ri-li<2*k) continue;
			if(li>0 and s[li-1]==s[li-1+k]) continue;
			if(ri<(int)s.size() and s[ri]==s[ri-k]) continue;
			runs.push_back(make_tuple(li, ri, k));
		}
	};

	f(false);
	f(true);
}

vector<tuple<int, int, int>>enum_run(string &s) {
	vector<tuple<int, int, int>>runs;
	enum_run_rec(0, s.size(), s, runs);
	sort(begin(runs), end(runs));
	vector<tuple<int, int, int>>ret;
	for(int i = 0 ; i <(int)runs.size() ; i ++) {
		if(i>0 and get<0>(runs[i])==get<0>(runs[i-1]) and get<1>(runs[i])==get<1>(runs[i-1])) {
			continue;
		}
		auto [l, r, t] = runs[i];
		ret.push_back(make_tuple(t, l, r));
	}
	return ret;
}

void solve() {
	int k; cin >> k;
	string s; cin >> s;

	if(k==1) {
		cout << 1ll*s.size()*(s.size()+1)/2 << endl;
		return;
	}

	auto vec = enum_run(s);

	ll ans = 0;
	for(auto &[t, l, r]: vec) {
		//cout << t << ' ' << l << ' ' << r << endl;
		for(int len = t ; k*len <= r-l ; len += t){
			ans += r-l-k*len+1;
		}
	}
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t; cin >> t;
	while(t--) {
		solve();
	}

	return 0;
}