#include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int T, n, ans; cin >> T; while(T--){ string s; cin >> n >> s; auto za = atcoder::z_algorithm(s + "`"); ans = 0; for(int i = 1; i < n; i++){ ans += za[i] >= i ? i < min(za[i], n - i) : s[za[i]] < s[i + za[i]]; } cout << ans << '\n'; } }