# ナイーブはTLE
# 文字列高速判定、LCPも考えたけど、比べる相手は1つだけ
# SA, PAを組み合わせるのはありえるのかもしれない
# SAとPAを1つのリストにしてソート、その順位を記録
# N回チェックすれば答えわかるか

T = int(input())
for t in range(T):
    N = int(input())
    S = input()
    L = []
    for i in range(1, N):
        U = S[:i]
        V = S[i:]
        L.append((U, i, 0))
        L.append((V, i, 1))
    L.sort()

    #print(L)

    order = [[-1]*2 for i in range(N+1)]
    for j in range(len(L)):
        uv, i, t = L[j]
        order[i][t] = j

    #print(order)

    ans = 0
    for i in range(1, N):
        if order[i][0] < order[i][1]:
            ans += 1
    print(ans)