Longest Repeated Substring

Given a string \(s\) of length \(n\), your task is to find the length of the longest substring that appears at least twice in \(s\). Formally, find the maximum \(L\) such that there exists a substring \(s[i..i+L-1]\) which occurs at least twice (the occurrences may overlap). If no such substring exists, output 0.

Note that the problem can be solved efficiently using binary search combined with a sliding window technique to check if a substring of a given length appears at least twice.

Example:

• For \(s = \texttt{\"banana\"}\), the longest repeated substring is \(\texttt{\"ana\"}\) with length 3.
• For \(s = \texttt{\"abcdef\"}\), there is no repeated substring so the answer is 0.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a string \(s\). You need to process each test case independently.

Input Format:

T
s1
s2
...
sT

outputFormat

For each test case, output one line containing a single integer denoting the length of the longest substring that appears at least twice in the input string.

Output Format:

result1
result2
...
resultT

## sample

3
banana
abcdef
aaaaa

3
0
4

</p>