H. Standoff
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of lowercase English letters.

Find two non-empty substrings$$$^{\text{∗}}$$$ $$$p$$$ and $$$q$$$ of $$$s$$$ such that $$$p$$$ is not a substring of $$$q$$$, and $$$q$$$ is not a substring of $$$p$$$. Note that $$$p$$$ and $$$q$$$ do not have to be disjoint — they may correspond to overlapping positions in $$$s$$$. Over all such pairs $$$(p, q)$$$, output the maximum possible value of $$$|p| + |q|$$$, where $$$|x|$$$ denotes the length of a string $$$x$$$.

If no such pair exists, output $$$0$$$.

$$$^{\text{∗}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end. For example, $$$\texttt{us}$$$ is a substring of $$$\texttt{sust}$$$, but $$$\texttt{ut}$$$ and $$$\texttt{aus}$$$ are not.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$) consisting of lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum value of $$$|p| + |q|$$$ over all valid pairs, or $$$0$$$ if no valid pair exists.

Example
Input
2
ab
z
Output
2
0
Note

In the first test case, $$$s = \texttt{ab}$$$. Choose $$$p = \texttt{a}$$$ and $$$q = \texttt{b}$$$; neither string is a substring of the other, and $$$|p| + |q| = 1 + 1 = 2$$$, which is the maximum possible.

In the second test case, $$$s = \texttt{z}$$$ has only one substring, $$$\texttt{z}$$$ itself, so the only possible choice is $$$p = q = \texttt{z}$$$. But then $$$p$$$ is a substring of $$$q$$$, so this pair is not valid. No valid pair exists, and the answer is $$$0$$$.