#include <bits/stdc++.h> using namespace std; #include <atcoder/string> using namespace atcoder; using ll = long long; using P = pair<ll,ll>; #define fix(x) fixed << setprecision(x) #define asc(x) x, vector<x>, greater<x> #define rep(i, n) for(ll i = 0; i < n; i++) #define all(x) (x).begin(),(x).end() template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;} constexpr ll INFLL = (1LL << 62), MOD = 998244353; constexpr int INF = (1 << 30); int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int t; cin >> t; while(t--){ int cnt = 0, n; string s; cin >> n >> s; auto x = z_algorithm(s); for(int i=1;i<n;i++){ if(x[i]<i) cnt += (s[x[i]] < s[i+x[i]]); else if(i<n-i) cnt++; } cout << cnt << '\n'; } return 0; }