#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)std::cerr<<x[_]<<' ';std::cerr<<'\n',aaa
#define dbgs(x) std::cerr<<(#x)<<"[stl]: ";for(auto _:x)std::cerr<<_<<' ';std::cerr<<'\n',aaa
#define dbgp(x) std::cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define dbgsp(x) std::cerr<<(#x)<<"[stl pair]:\n";for(auto _:x)std::cerr<<_.fi<<' '<<_.se<<'\n';aaa
#define maxn 1000000

using namespace std;

ifstream fin("prefix.in");
ofstream fout("prefix.out");

int lps[maxn+5];
const pii mod = pii(1000000007, 1000000009);
pii p27[maxn+5];

struct hasher {
  int n;
  string s;
  vector<pii> pref;

  hasher (string s_, int n_) {
    s = s_;
    n = n_;
    assert(sz(s) == n+1); /// " " + ...

    pref.resize(n+1, pii(0, 0));
    for (int i = 1; i <= n; i++) {
      pref[i].fi = ((ll)pref[i-1].fi * 27 + s[i] - 'a' + 1) % mod.fi;
      pref[i].se = ((ll)pref[i-1].se * 27 + s[i] - 'a' + 1) % mod.se;
    }
  }


  ///hash pentru [l, r].
  pii cut (int l, int r) {
    if (l > r) swap(l, r);

    assert(1 <= l);
    assert(r <= n);

    pii sol;

    sol.fi = (pref[r].fi - (ll)pref[l-1].fi * p27[r-l+1].fi % mod.fi + mod.fi) % mod.fi;
    sol.se = (pref[r].se - (ll)pref[l-1].se * p27[r-l+1].se % mod.se + mod.se) % mod.se;

    return sol;
  }
};

void solver() {
  string s; fin >> s;
  int n = sz(s);
  s = " " + s;

  int i, j, z;

  lps[0] = lps[1] = 0;
  for (i = 2; i <= n; i++) {
    if (s[lps[i-1]+1] == s[i]) {
      lps[i] = 1 + lps[i-1];
    } else {
      j = i;
      while (j > 0 && s[lps[j-1]+1] != s[i]) {
        j = lps[j-1];
      }

      if (j > 0) {
        lps[i] = lps[j-1] + 1;
      } else {
        lps[i] = 0;
      }
    }
  }

//  dbga(lps, n+1);

  ///pentru un prefix anume din string, ma folosesc de lps astfel:
  ///[-----==========].....
  ///.....[==========-----]
  ///pp ca [-] este cel mai lung prefix diferit de tot sirul csd curent care este si sufix.
  ///portiunea comuna este la fel, daca vr ca sirul curent sa fie concatenare de aceleasi prefixe, trb ca
  ///.. ramase in fata sa fie la fel ca .. ramase in spate, iar lps[x] * 2 >= x.

  hasher H(s, n);
  int ans = 0;

  for (i = 1; i <= n; i++) {
    if (2 * lps[i] >= i && H.cut(1, i-lps[i]) == H.cut(lps[i]+1, i)) {
      ans = i;
    }
  }

  fout << ans << '\n';
}

int main () {
  p27[0] = pii(1, 1);
  for (int i = 1; i <= maxn; i++) {
    p27[i].fi = (ll)p27[i-1].fi * 27 % mod.fi;
    p27[i].se = (ll)p27[i-1].se * 27 % mod.se;
  }

  int t; fin >> t;
  while (t--) solver();

  fin.close();
  fout.close();

  return 0;
}