import java.util.Scanner;

public class Main {
    static int N=1000000;
    static char[] s=new char[N];
    static char[] str=new char[N*2+3];
    static int[] p=new int[N*2+2];
    static int n;
    public static void main(String[] args) throws Exception {
        Scanner st=new Scanner(System.in);
        int n1=st.nextInt();
        st.nextLine();
        if (n1<=30) {
            while (n1-->0) { 
                String string=st.nextLine();
//              for (int i = 0; i < N; i++) {
//                  s[i]='a';
//          }
                s=string.toCharArray();
                pre();
            kp();
            pt(); }
            }
    }
    public static void pt() {
        // TODO Auto-generated method stub
        int i;
        int ans = 0;
        for(i=0;i<n;i++)
            ans=Math.max(ans, p[i]);
        System.out.printf("%d\n", ans-1);

    }
public static void kp() {
        // TODO Auto-generated method stub
        int i;
        int mx = 0;
        int id=0;
        for(i=1; i<n; i++){
            if( mx > i )
                p[i] = Math.min( p[2*id-i], p[id]+id-i );
            else
                p[i] = 1;
            for(; str[i+p[i]] == str[i-p[i]]; p[i]++) ;
            if( p[i] + i > mx ) {
                mx = p[i] + i;
                id = i;
            }
        }
    }
    public static void pre() {
        // TODO Auto-generated method stub
        int i,j,k;
        n = s.length;
        str[0] = '$';
        str[1] = '#';
        for(i=0;i<n;i++)
        {
            str[i*2 + 2] = s[i];
            str[i*2 + 3] = '#';
        }
        n = n*2 + 2;
        str[n] = 0;
    }
}