public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		StringBuilder out = new StringBuilder();
		while ((line = in.readLine()) != null && line.length() != 0) {
			int nSet = Integer.parseInt(line.trim());
			for (int t = 0; t < nSet; t++) {
				String a = in.readLine().trim();
				cad = a.toCharArray();
				comp = new theComparator(cad);
				int[] sa = suffixArray();
				int[] lcp = lcp(sa);
				int max = 0;
				for (int i = 0; i < lcp.length; i++)
					max = Math.max(max, lcp[i]);
				out.append(max + "\n");
			}
		}
		System.out.print(out);
	}