#include <bits/stdc++.h>
using namespace std;
int lps(string);
int main()
{
//code
int T;
cin >> T;
getchar();
while (T–) {
string s;
cin >> s;
printf("% d\n", lps(s));
}
return 0;
}
int lps(string s)
{
int n = s.size();
int lps[n];
int i = 1, j = 0;
lps[0] = 0;
while (i < n) {
if (s[i] == s[j]) {
j++;
lps[i] = j;
i++;
}
else {
if (j != 0)
j = lps[j – 1];
else {
lps[i] = 0;
i++;
}
}
}
return lps[n – 1];
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBscHMoc3RyaW5nKTsKaW50IG1haW4oKQp7CiAgICAvL2NvZGUKICAgIGludCBUOwogICAgY2luID4+IFQ7CiAgICBnZXRjaGFyKCk7CiAgICB3aGlsZSAoVOKAkykgewogICAgICAgIHN0cmluZyBzOwogICAgICAgIGNpbiA+PiBzOwogICAgICAgIHByaW50ZigiJSBkXG4iLCBscHMocykpOwogICAgfQogICAgcmV0dXJuIDA7Cn0KaW50IGxwcyhzdHJpbmcgcykKewogICAgaW50IG4gPSBzLnNpemUoKTsKICAgIGludCBscHNbbl07CiAgICBpbnQgaSA9IDEsIGogPSAwOwogICAgbHBzWzBdID0gMDsKICAgIHdoaWxlIChpIDwgbikgewogICAgICAgIGlmIChzW2ldID09IHNbal0pIHsKICAgICAgICAgICAgaisrOwogICAgICAgICAgICBscHNbaV0gPSBqOwogICAgICAgICAgICBpKys7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBpZiAoaiAhPSAwKQogICAgICAgICAgICAgICAgaiA9IGxwc1tqIOKAkyAxXTsKICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICBscHNbaV0gPSAwOwogICAgICAgICAgICAgICAgaSsrOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGxwc1tuIOKAkyAxXTsKfQ==