题目描述

一位天体生物学家正在研究 Alphabet 星球上的生命。在这颗星球上，生命的遗传物质由 $26$ 种核苷酸组成。因此，每种生命的基因组都可以表示为一个由小写英文字母组成的字符串。

生物学家已经确定了 $K$ 种生命形式的 DNA 序列，这些序列不一定互不相同，它们的总长度为 $N$。

她希望找到在这些生命形式的遗传代码中经常出现的连续 DNA 片段。

对于 $2\le i\le K$，定义 $L(i)$ 为：至少出现在 $i$ 个生命形式中的最长连续子串的长度。

注意，$L(i)$ 可以为 $0$。

请你计算整个序列：

输入格式

第一行包含一个整数 $K$，表示生命形式数量。

接下来 $K$ 行，每行包含一个非空的小写英文字母串。第 $i$ 个字符串表示第 $i$ 种生命形式的基因序列。

输出格式

包含 $K-1$ 行。

依次输出 $L(2),L(3),\ldots,L(K)$，每个值单独占一行。

约束

• $2 \le N \le 200000$。
• $2 \le K \le N$。

子任务

• 测试点单独计分。
• 子任务 1（30%）：$N \le 10000$。
• 子任务 2（40%）：$N \le 100000$。
• 子任务 3（30%）：原始约束。

样例

输入

6
matter
animate
pattern
thermal
domain
teammate

输出

5
3
2
2
1

样例解释

• atter 出现在两个字符串中；
• mat 出现在三个字符串中；
• ma、at 或 te 出现在四个字符串中；
• ma 出现在五个字符串中；
• a 出现在所有字符串中。