/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * OK, 0.217 sec
 */

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

typedef unsigned long long ull;

const int maxn = 2e5 + 10;
const int P = 239017;

char s[maxn];
ull h[maxn], deg[maxn];
int tn, n;

inline ull str( int l, int r ) // [l,r)
{
  return h[r] - h[l] * deg[r - l];
}

inline int check( int T, int L, int R )
{
  return R - L <= T || str(L, R - T) == str(L + T, R);
}

int check( int T, int L1, int R1, int L2, int R2 ) // [L1,R1) [L2,R2)
{
  if (!check(T, L1, R1)) return 0;
  if (!check(T, L2, R2)) return 0;
 
  int X1 = min(T, R1 - L1);
  if (L2 + T - X1 >= R2)
    return 1;
  int X2 = max(0, L2 + T - R2);
  return str(R1 - X1, R1 - X2) == str(L2 + T - X1, L2 + T - X2);
}

int main()
{
  deg[0] = 1;
  forn(i, maxn - 1)
    deg[i + 1] = deg[i] * P;

  scanf("%d", &tn);
  while (tn--)
  {
    scanf("%d%s", &n, s);

    int mi = n;
    forn(t, 2)
    {
      reverse(s, s + n);
      h[0] = 0;
      forn(i, n)
        h[i + 1] = h[i] * P + s[i];

      int l;
      for (l = 1; l < n; l++)
      {
        int L, R, M;
        L = 0, R = n;
        while (L < R)
          if (check(l, 0, M = (L + R + 1) / 2))
            L = M;
          else
            R = M - 1;
        if (check(l, 0, L, L + 1, n))
          break;
      }
      mi = min(mi, l);
    }
    printf("%d\n", mi);
  }
}
