import java.util.Scanner;

public class HihoCoder1032 {

	public static void main(String arg[]) {
		Scanner in = new Scanner(System.in);
		int count = in.nextInt();
		while (count-- > 0) {
			String item = in.next();
			handle(item);
		}
	}

	public static void handle(String s) {
		int s_len = s.length();
		char[] ch = s.toCharArray();
		String[] value = new String[2 * s_len + 3];
		value[0] = "$";
		value[1] = "#";
		value[value.length - 1] = "@";
		for (int i = 0, j = 2; i < s_len; ++i) {
			value[j++] = String.valueOf(ch[i]);
			value[j++] = "#";
		}

		int new_value_len = value.length;
		int[] p = new int[new_value_len + 1];
		int id = 0;// 记录已经查找过的边界最靠右回文串的中心
		int mx = 0;
		p[0] = 1;
		for (int i = 1; i < p.length; i++) {
			if (mx > 1) {
				p[i] = p[2*id-i] < mx-i ? p[2*id-i] : mx - i;
			} else {
				p[i] = 1;
			}
			while ((i + p[i] < p.length-1 )&& (i - p[i] >= 0 )&& (value[i + p[i]].equals(value[i - p[i]]))) {
				p[i] += 1;
			}
			if (i + p[i] > mx) {
				mx = i + p[i];
				id = i;
			}

		}
		int max=0;
		for(int a :p){
			max=max>a?max:a;
		}
		System.out.println(max - 1);

	}

/*	public static void getValue(String s) {
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length(); i++) {

			String tmp = getEvery(s, i, i);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
			tmp = getEvery(s, i, i + 1);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
		}
		System.out.println(longest.length());
	}

	public static String getEvery(String s, int begin, int end) {
		int length = s.length();
		while (begin >= 0 && end <= length - 1 && s.charAt(begin) == s.charAt(end)) {
			begin--;
			end++;
		}
		return s.substring(begin + 1, end);
	}*/
}