Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3199
Longest Repeated Substring

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Write a program that takes a string and returns length of the longest repeated substring. A repeated substring is a sequence of characters that is immediately followed by itself.

For example, given "Mississippi", the longest repeated substring is "iss" or "ssi" (not "issi").
Given "Massachusetts", the longest repeated substring would be either "s" or "t".
Given "Maine", the longest repeated substring is "" (the empty string).

Input

The first line of the input contains a single integer T , the number of test cases.

Each of the following T lines, is exactly one string of lowercase charactors.

The length of each string is at most 50000 characters.

Output

For each test case, print the length of the Longest Repeated Substring.

Sample Input

2
aaabcabc
ab

Sample Output

3
0

Author: PENG, Peng
Source: ZOJ Monthly, May 2009
Submit    Status