#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
pair<long long int, long long int> operator+(
    pair<long long int, long long int> a,
    pair<long long int, long long int> b) {
  return {a.first + b.first, (a.second + b.second) % 1000000321};
}
pair<long long int, long long int> operator*(
    pair<long long int, long long int> a,
    pair<long long int, long long int> b) {
  return {a.first * b.first, (a.second * b.second) % 1000000321};
}
pair<long long int, long long int> operator-(
    pair<long long int, long long int> a,
    pair<long long int, long long int> b) {
  return {a.first - b.first, (a.second + 1000000321 - b.second) % 1000000321};
}
mt19937 gen(__builtin_ia32_rdtsc());
uniform_int_distribution<long long int> dist(256, 1000000321 - 1);
string s;
pair<long long int, long long int> p[5010], h[5010];
long long int n, suff[5010];
long long int lcp(long long int i, long long int j, long long int l,
                  long long int r) {
  if (l == r) return l;
  long long int m = (l + r + 1) / 2;
  return ((h[(i) + (m)] - h[i] * p[m]) == (h[(j) + (m)] - h[j] * p[m]))
             ? lcp(i, j, m, r)
             : lcp(i, j, l, m - 1);
}
bool lexLess(long long int i, long long int lI, long long int j,
             long long int lJ) {
  if (((h[(i) + (min(lI, lJ))] - h[i] * p[min(lI, lJ)]) ==
       (h[(j) + (min(lI, lJ))] - h[j] * p[min(lI, lJ)])))
    return lI < lJ;
  long long int m = lcp(i, j, 0, min(lI, lJ) - 1);
  return s[i + m] < s[j + m];
}
long long int bt[5010], rmq[5010][13];
long long int f(long long int a, long long int b) { return min(a, b); }
long long int query(long long int l, long long int r) {
  return f(rmq[l][bt[r - l]], rmq[r - (1 << bt[r - l])][bt[r - l]]);
}
long long int dp[5010], id[5010];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (long long int j = 0; j < (13); ++j)
    for (long long int i = (1 << j); i < (min(5010, 1 << (j + 1))); ++i)
      bt[i] = j;
  long long int tc;
  cin >> tc;
  while (tc--) {
    cin >> n >> s;
    p[0] = {1, 1}, p[1] = {dist(gen) | 1, dist(gen)};
    for (long long int i = 1; i < (s.size() + 1); ++i)
      p[i] = p[i - 1] * p[1],
      h[i] = h[i - 1] * p[1] +
             pair<long long int, long long int>{s[i - 1], s[i - 1]};
    iota(suff, suff + n, 0);
    sort(suff, suff + n, [](long long int i, long long int j) {
      return lexLess(i, n - i, j, n - j);
    });
    for (long long int i = 0; i < (n); ++i) id[suff[i]] = i;
    for (long long int i = 0; i < (n - 1); ++i)
      rmq[i][0] =
          lcp(suff[i], suff[i + 1], 0, min(n - suff[i], n - suff[i + 1]));
    for (long long int j = 1; j < (13); ++j)
      for (long long int i = 0; i < (n - 1); ++i) {
        long long int i2 = i + (1 << (j - 1));
        if (i2 < n)
          rmq[i][j] = f(rmq[i][j - 1], rmq[i2][j - 1]);
        else
          rmq[i][j] = rmq[i][j - 1];
      }
    for (long long int i = n - 1; i > (-1); --i) {
      dp[i] = n - i;
      for (long long int j = i + 1; j < (n); ++j)
        if (id[j] > id[i])
          dp[i] = max(dp[i], dp[j] + n - i - query(id[i], id[j]));
    }
    cout << *max_element(dp, dp + n) << '\n';
  }
}
