#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <map>

 #include <vector>

 #include <stack>

 #include <string>

 #include <ctime>

 #include <queue>

 #define mem0(a) memset(a, 0, sizeof(a))

 #define mem(a, b) memset(a, b, sizeof(a))

 #define lson l, m, rt << 1

 #define rson m + 1, r, rt << 1 | 1

 #define eps 0.0000001

 #define lowbit(x) ((x) & -(x))

 #define memc(a, b) memcpy(a, b, sizeof(b))

 #define x_x(a) ((a) * (a))

 #define LL long long

 #define DB double

 #define pi 3.14159265359

 #define MD 10000007

 #define INF (int)1e9

 #define max(a, b) ((a) > (b)? (a) : (b))

 using namespace std;

 char str[];

 int next[];

 void getNext()

 {

         next[] = next[] = ;

         for(int i = ; str[i]; i++) {

                 int j = next[i];

                 while(j && str[i] != str[j]) j = next[j];

                 next[i + ] = str[i] == str[j]? j +  : ;

         }

 }

 int solve()

 {

         int len = strlen(str), ans = next[len], F = ;

         while(ans *  > len) ans = next[ans];

         while(ans) {

                 for(int i = ans * ; i <= len - ans; i++) {

                         int j = next[i];

                         while(j > ans) j = next[j];

                         if(j == ans) {

                                 F = ;

                                 break;

                         }

                 }

                 if(F) break;

                 ans = next[ans];

         }

         return ans;

 }

 int main()

 {

         //freopen("input.txt", "r", stdin);

         int T;

         cin>> T;

         for(int i = ; i <= T; i++) {

                 scanf("%s", str);

                 getNext();

                 cout<< solve()<< endl;

         }

         return ;

 }