// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 5e5 + 5;

struct SAM{
	int len, nxt[26], link;
} t[N << 1];

int last, idx, n, sz[N << 1], pos[N << 1];

char s[N];

void inline init() {
	last = idx = 1;
}

vector<int> g[N << 1];

void inline clr() {
	for (int i = 1; i <= idx; i++) {
		for (int j = 0; j < 26; j++) t[i].nxt[j] = 0;
		t[i].link = t[i].len = pos[i] = sz[i] = 0;
		g[i].clear();
	}
	idx = last = 0;
}

void extend(int c) {
	int x = ++idx, p = last; sz[x]++; t[x].len = t[p].len + 1;
	while (p && !t[p].nxt[c]) t[p].nxt[c] = x, p = t[p].link;
	if (!p) t[x].link = 1;
	else {
		int q = t[p].nxt[c];
		if (t[p].len + 1 == t[q].len) {
			t[x].link = q;
		} else {
			int y = ++idx;
			t[y] = t[q];
			t[y].len = t[p].len + 1;
			while (p && t[p].nxt[c] == q) 
				t[p].nxt[c] = y, p = t[p].link;
			t[x].link = t[q].link = y;
		}
	}
	last = x;
}

int ans;

void dfs(int u) {
	for (int v: g[u]) {
		dfs(v);
		sz[u] += sz[v];
		if (pos[v]) {
			if (!pos[u]) pos[u] = pos[v];
			else chkMin(pos[u], pos[v]);
		}
	}
	if (sz[u] > 1) chkMax(ans, t[u].len + (n - pos[u]) / 2);
}

int main() {
	int T; read(T);
    while (T--) {
    	init();
    	scanf("%s", s + 1); n = strlen(s + 1);
    	ans = n / 2;
    	for (int i = 1; i <= n; i++) extend(s[i] - 'a'), pos[last] = i;
    	for (int i = 2; i <= idx; i++) g[t[i].link].pb(i);
    	dfs(1);
    	printf("%d\n", ans);
    	clr();
    }
    return 0;
}