T = int(input())
for _ in range(T):
    N = int(input())
    S = input().strip()
    Z = [0]*N
    Z[0] = N
    l = 0
    r = -1
    for i in range(1,N):
        if i>r:
            k = 0
            l = i
            r = i-1
            while i+k<N and S[k]==S[i+k]:
                k += 1
                r += 1
            Z[i] = k
            continue
        Z[i] = min(Z[i-l],r-i+1)
    ans = 0
    for i in range(1,N):
        if Z[i]<i and i+Z[i]<N and S[Z[i]]<S[i+Z[i]]:
            ans += 1
            continue
        if Z[i]>=i and i<N-1:
            ans += 1
    print(ans)