#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)

#define sz(x) (int)x.size()
#define eb emplace_back
#define pb push_back
#define pob pop_back
#define fi first
#define se second

#define overload4(a, b, c, d, name, ...) name
#define REP0(n) for(ll _abcde12345 = 0; _abcde12345 < (ll)(n); ++_abcde12345)
#define REP1(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define REP2(i, a, b) for(ll i = (a); i < (ll)(b); ++i)
#define REP3(i, a, b, c) for(ll i = (a); i < (ll)(b); i += (c))
#define rep(...) overload4(__VA_ARGS__, REP3, REP2, REP1, REP0)(__VA_ARGS__)
#define rrep(i, a, b) for(ll i = (a); i >= (ll)(b); --i)

#define each_for(...) for (auto&& __VA_ARGS__)
#define each_const(...) for (const auto& __VA_ARGS__)

#define yesno(bool) if(bool) { cout << "Yes\n"; } else { cout << "No\n"; }
#define ifelse(bool, x, y) if(bool) { cout << (x) << '\n'; } else { cout << (y) << '\n'; }

#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()

#define fix fixed << setprecision(15)

#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))

#define NP(v) next_permutation(all(v))
#define SORT(v) sort(all(v))
#define SORT2(v) sort(rall(v))
#define REV(v) reverse(all(v))
#define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end())
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define COUNT(v,x) count(all(v),x)

#define Mod 1000000007
#define mod 998244353

#define inf 1001001001
#define infl 1001002003004005006ll

#define fast ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr)

#define drop(x) { cout << (x) << endl; return; }

using ll = long long;
using lint = long long;
using i64 = long long;
using ld = long double;
using Mint = modint1000000007;
using mint = modint998244353;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvvi = vector<vvi>;
using vvvl = vector<vvl>;
using vvvvi = vector<vvvi>;
using vvvvl = vector<vvvl>;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vvvvb = vector<vvvb>;

const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };
const int dx8[] = { 0,1,0,-1,1,-1,1,-1 };
const int dy8[] = { 1,0,-1,0,1,1,-1,-1 };

template<class T>ostream &operator<<(ostream &os,const vector<T> &v)
{
	for(int i=0;i<(int)v.size();++i)
	{
		os<<v[i]<<(i+1!=(int)v.size()?" ":"");
	}
	return os;
}

template<class T>ostream &operator<<(ostream& os,const vector<vector<T>> &v)
{
	for(int i=0;i<(int)v.size();++i)
	{
		for(int j=0;j<(int)v[i].size();++j)
		{
			os<<v[i][j]<<(j+1!=(int)v[i].size()?" ":"");
		}
		os<<(i+1!=(int)v.size()?"\n":"");
	}
	return os;
}

template<class T>istream &operator>>(istream &is,vector<T> &v)
{
	for(T &in:v)is>>in;
	return is;
}

template<class T>istream &operator>>(istream &is,vector<vector<T>> &v)
{
	for(vector<T> &v2:v)for(T &in:v2)is>>in;
	return is;
}

template<class T,class S>inline bool chmax(T& a,const S& b){return(a<b?a=b,1:0);}
template<class T,class S>inline bool chmin(T& a,const S& b){return(a>b?a=b,1:0);}

long long POW(long long A,long long B)
{
	long long ret=1;
	while(B>0)
	{
		if(B&1)ret*=A;
		A*=A;
		B>>=1;
	}
	return ret;
}

long long modpow(long long A,long long B,long long MOD)
{
	long long ret=1;
	while(B>0)
	{
		if(B&1)ret=ret*A%MOD;
		A=A*A%MOD;
		B>>=1;
	}
	return ret;
}

bool is_prime(long long X)
{
	for(long long i=2;i*i<=X;++i)if(X%i==0)return false;
	return true;
}

vector<long long>divisor(long long X)
{
	vector<long long>ret;
	for(long long i=1;i*i<=X;++i)if(X%i==0)
	{
		ret.push_back(i);
		if(i!=X/i)ret.push_back(X/i);
	}
	return ret;
}

vector<long long>prime_factor(long long X)
{
	vector<long long>ret;
	for(long long i=2;i*i<=X;++i)
	{
		while(X%i==0)
		{
			X/=i;
			ret.push_back(i);
		}
	}
	if(X>1)ret.push_back(X);
	return ret;
}

vector<long long>sieve(long long X)
{
	vector<long long>ret;
	vector<bool>F(X+1);
	for(long long i=2;i<=X;++i)if(!F[i])
	{
		ret.push_back(i);
		for(long long j=i+i;j<=X;j+=i)F[j]=true;
	}
	return ret;
}

/**********************************************************************************************************/



void solve();

//#define int long long

signed main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	cout<<fixed<<setprecision(15);

	int T=1;

	cin>>T;
	
	rep(T)solve();

	return 0;
}

/////////////////////////////////////////////////////////////



void solve()
{
	int N;
	string S;
	cin>>N>>S;
	vi A=z_algorithm(S);
	int ans=0;
	rep(i,1,N)
	{
		int x=min<int>(A[i],i);
		if(i>x)
		{
			if(i+x<N&&S[x]<S[i+x])
			{
				ans++;
				continue;
			}
		}
		else if(i<N-i)
		{
			ans++;
		}
	}
	cout<<ans<<endl;
}