To help you better understand the problem, here are some definitions regarding 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$, $T$ is called a substring of $S$ if $m = 0$ (i.e., $T$ is an 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 if $i$ can be $1$ in the condition above, $T$ is called a prefix of $S$; if $m = 0$ or if $j$ can be $n$ in the condition above, $T$ is called a suffix of $S$.

Given a string $S$ consisting of lowercase English letters, you need to find the longest possible sequence of strings $(T_0, T_1, \ldots, T_l)$ such that:

• $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$ of length $\lvert T_{i - 1} \rvert$ is $T_{i - 1}$, and the suffix of $S'_i$ of length $\lvert T_i \rvert$ is $T_i$.

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

Input

This problem contains multiple test cases.

The first line of input contains an integer $T$, representing the number of test cases. For each test case, the input consists of a single line containing a string $S$ composed of lowercase English letters.

Output

For each test case, output a single integer representing the maximum length of the string sequence as described in the problem.

Examples

Input 1

3
abcd
abab
a

Output 1

2
3
0

Note 1

In the following, the symbol $\epsilon$ is used to denote the empty string.

For the first test case, one possible string sequence is: $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, one possible string sequence is: $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, one possible string sequence is: $T_0 = \epsilon$.

Examples 2

See the provided files.

The strings in this sample have a certain gradient in length; you can use this sample to check your program.

Examples 3

See the provided files.

This sample satisfies special property A.

Subtasks

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

For $100 \%$ of the test data, $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 from the lowercase English alphabet.

Note

The input and output volume for this problem is large; please use efficient input and output methods.

For example, if your code uses cin and cout, you may choose to add the following statements after your input/output redirection statements (freopen, fopen, etc.) to accelerate input and output:

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

It is not recommended to mix cin, cout with other input/output methods after adding these statements.