You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

在 CQUPT（重庆邮电大学） 的某个神秘实验室里，
奶龙正在测试一套 3G 超远古信号发送系统。

由于 3G 网络极其不稳定，每次发送字符串信号时，
都会随机丢失一个字符。

奶龙觉得这太不抽象了，于是他决定：
我自己来决定删哪一位！

题目描述

给定一个长度为 n 的字符串 s。

对于每一个位置 i (1 ≤ i ≤ n)，定义 $t_i$ 为：

从字符串 s 中 删除第 i 个字符 后得到的字符串
（其余字符的相对顺序保持不变）

最长公共前缀（LCP）

对于两个字符串 x 和 y，
定义 lcp(x, y) 为它们的 最长公共前缀长度，即：

最大的整数 ℓ ≥ 0，使得
x[1..ℓ] = y[1..ℓ]

奶龙的问题

奶龙会选择 两个不同的位置 i ≠ j 进行删除操作，
得到字符串 $t_i$ 与 $t_j$。

请你帮奶龙计算：

所有 i ≠ j 中
$lcp(t_i, t_j)$ 的最大值

形式化地，你需要求：

$\max_{1 \le i < j \le n} lcp(t_i, t_j)$

⚠️ 注意：
你 不需要输出位置 i 和 j，只需输出最大值。

Input Format

第一行一个整数 T，表示测试用例数量
$(1 ≤ T ≤ 2 × 10^5)$

接下来 T 行，每行一个字符串 s，满足： $2 ≤ |s| ≤ 5 × 10^5$ 仅包含小写英文字母
所有测试用例中 |s| 的总和不超过 $5 × 10^5$

Output Format

对于每个测试用例，输出一行一个整数，
表示最大可能的 $lcp(t_i, t_j)$。

Sample

样例 1

输入

5
abac
abbbb
cbacb
babcc
aa

输出

2
4
3
4
1

解释（非唯一方案）

• 对于字符串 abac： 删除第 3 位字符 'a' 与删除第 4 位字符 'c'，得到的字符串分别为 abc 与 aba，其最长公共前缀长度为 2，这是可以达到的最大值。

• 对于字符串 abbbb： 删除任意一个 'b'，得到的字符串均为 abbb， 因此最长公共前缀长度为 4。

• 对于字符串 cbacb： 可以选取合适的两个删除位置，使得得到的字符串在前 3 个字符完全一致。

• 对于字符串 babcc： 删除相邻相同字符 'c' 中的任意一个， 可以得到两个完全相同的字符串，最长公共前缀长度为 4。

• 对于字符串 aa： 删除任意一个字符后均得到 "a"， 最长公共前缀长度为 1。

样例 2

输入

1
abcde

输出

3

Hint

字符串 $$s$$ 仅由小写英文字母组成, 所有测试用例中字符串长度之和不超过 $5 \times 10^5$