#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int  maxn = 1000000+10;
int next[maxn],n;
char str[maxn];

void getNext(){
    next[0] = next[1] = 0;
    for(int i = 1,j; i < n; i++){
        j = next[i];
        while(j && str[i] != str[j]) j = next[j];
        if(str[i] == str[j]) next[i+1] = j+1;
        else next[i+1] = 0;
    }
}

bool find(int ed){
    int cnt = 0;
    for(int i = 0,j = 0; i < n; i++){
        while(j && str[i] != str[j]) j = next[j];
        if(str[i]==str[j]) j++;
        if(j==ed){
            ++cnt;
            j = 0;
            if(cnt>=3) return true;
        }
    }
    return false;
}

int binary_search(){
    int L = 1,R = n/3+1,mid;
    while(L <= R){
        mid = (L+R)>>1;
        if(find(mid)){
            L = mid+1;
        }else{
            R = mid-1;
        }
    }
    if(find(L)) return L;
    else if(find(R)) return R;
    else return  L-1;

}

int main(){

    int ncase;
    cin >>  ncase;
    while(ncase--){
        scanf("%s",str);
        n = strlen(str);
        getNext();
        printf("%d\n",binary_search());
    }
    return 0;
}