409345: GYM103486 L Suzuran Loves String

Miss Suzuran is the light of us.

Tonight Suzuran is learning string data structures. Learning the suffix tree, she wonders how long is the 'diameter' of a suffix tree. Formally, Suzuran has a string $$$S$$$ of length $$$n$$$. Now she can apply the following operations on a string $$$s$$$.

• Delete one character from the end of $$$s$$$.
• Add one character to the end of $$$s$$$.

She defines the distance of suffix $$$A$$$ and suffix $$$B$$$, which is denoted as $$$d(A, B)$$$, the mininum number of operations you need to apply on $$$A$$$ to make it same as $$$B$$$.

Of course, string $$$S$$$ has $$$n$$$ different suffixes. Suzuran refers to the suffix begins at $$$i$$$-th position as $$$s_i (0 \leq i < n)$$$. She wonders the maximum value of $$$d(s_i, s_j) (0 \leq i < j < n)$$$. She tries to solve this problem with string data structures, but it seems too complicated to her.

So Suzuran comes to you. Try to teach Suzuran a simple way to solve it, so that she could go bed on time and presenting Doctor Kal'sist from madness and you from sleeping on the bridge of the ship.

By the way, as a gentle girl, Suzuran tells you the definition of "suffix": if string $$$A$$$ is a suffix of string $$$B$$$, you could obtain $$$A$$$ by deleting several (possibly zero) characters from the beginning of $$$B$$$.

The first line contains an integer $$$T$$$, refering to the number of test cases.

For each test case, there is only one line, containing a string $$$S$$$ that Suzuran brings to you.

The strings only contain lowercase English letters.

It guaranteened that $$$2 \leq |S| \leq 1000000, \sum |S| \leq 5000000$$$.

For each test case, output one integer, refering to the maximum value of $$$d(s_i, s_j) (0 \leq i < j < n)$$$.

1
doctor

11

For string "doctor", you pick suffix "doctor" and suffix "octor". And you need to delete 'r', 'o', 't', 'c', 'o', 'd' from the end of string "doctor" one by one and then add 'o', 'c', 't', 'o', 'r' to the end to make suffix "doctor" the same as suffix "octor". There is no way to pick suffixes to get a bigger distance, so the answer is 11.