Problem Description

To help you better understand the statement, here are some definitions about strings:

• For a string $S = s_1 s_2 \cdots s_n$, its length is defined as $\lvert S \rvert = n$.
• For two strings $S = s_1 s_2 \cdots s_n$ and $T = t_1 t_2 \cdots t_m$, we call $T$ a substring of $S$ if $m = 0$ (i.e., $T$ is the empty string) or $\exists 1 \le i \le j \le n$ such that $T = s_i s_{i + 1} \cdots s_j$. If $m = 0$ or in the above condition $i$ can be $1$, then $T$ is called a prefix of $S$; if $m = 0$ or in the above condition $j$ can be $n$, then $T$ is called a suffix of $S$.

Given a string $S$ consisting of lowercase English letters, you need to find a string sequence $(T_0, T_1, \ldots, T_l)$ that is as long as possible, satisfying:

• $T_0$ is a substring of $S$.
• $\forall 1 \le i \le l$, $\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$.
• $\forall 1 \le i \le l$, there exists a substring $S'_i$ of $S$ with length $\lvert T_i \rvert + 1$, such that the prefix of $S'_i$ with length $\lvert T_{i - 1} \rvert$ is $T_{i - 1}$, and the suffix of $S'_i$ with length $\lvert T_i \rvert$ is $T_i$.

Output the maximum possible length of such a sequence (i.e., the maximum value of $l$).

Input Format

This problem has multiple test cases. The first line contains an integer $T$, denoting the number of test cases. For each test case, one line contains a string $S$ consisting of lowercase English letters.

Output Format

For each test case, output one integer per line, representing the maximum length of the string sequence described in the statement.

3
abcd
abab
a

2
3
0

Hint

[Sample Explanation #1]

In the following, the symbol $\epsilon$ denotes the empty string.

For the first test case, we can find the following string sequence: $T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{cd}$, where $S'_1 = \texttt{ab}, S'_2 = \texttt{bcd}$.

For the second test case, we can find the following string sequence: $T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{ab}, T_3 = \texttt{bab}$, where $S'_1 = \texttt{ab}, S'_2 = \texttt{bab}, S'_3 = \texttt{abab}$.

For the third test case, we can find the following string sequence: $T_0 = \epsilon$.

[Sample #2]

See the attachments string/string2.in and string/string2.ans.

The string lengths in this sample have some gradients. You can use this sample to check your program.

[Sample #3]

See the attachments string/string3.in and string/string3.ans.

This sample satisfies Special Property A.

[Constraints]

Let $\sum |S|$ denote the sum of string lengths of all test cases in a test.

For $100 \%$ of the testdata, $T \ge 1$, $1 \le \lvert S \rvert \le 5 \times {10}^5$, $1 \le \sum \lvert S \rvert \le 1.5 \times {10}^6$.

Special Property A: each character in the string is generated independently and uniformly at random among lowercase letters.

[Notes]

The input and output size of this problem is large, so please use faster I/O.

For example, if your code uses cin and cout for I/O, you may add the following statements after the I/O redirection statements (freopen, fopen, etc.) to speed up I/O.

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

After adding these statements, it is not recommended to use cin, cout together with other I/O methods.

Translated by ChatGPT 5