题目描述

依依是一个住在海边小镇的女孩，她的朋友们分散在世界的各个角落。他们有一个特殊的传递信息的方式，那就是通过海洋传递瓶中信。每个瓶中信里，都装着一串由小写英文字母组成的信息，代表一个友情的密码。

这个夏天，依依在海滩上捡到$N$个瓶中信，每个瓶中信里都有一条由小写英文字符组成的信息，这些信息分别来自她的$N$个朋友。我们记第i个朋友的信息为$S_i$，其中$i= 1,2,..., N$。

为了找出与自己最有缘分的朋友，依依决定比较这些信息的相似度。这里的"相似度"指的是两条信息从头开始，最长能够匹配的字符数量。

注意，依依并不想比较一条信息与它自身的相似度。

现在，依依希望你能帮助她找出对于每条信息$S$​，哪条信息与其最相似，即从开头开始，最长能连续匹配的字符的数量是多少。

输入格式

输入的第一行包含一个整数$N(1 \leqslant N \leqslant 10 ^ 4)$。

接下来的$N$行，每行包含一个由小写字符构成的字符串$S_i$，表示小蓝的一个朋友在信封里刻写的信息。$\sum\limits_{i = 1}^N \mid S_i \mid \leqslant 10^5$。

输出格式

输出共$N$行， 对于每条信息$S_i$, 输出一个整数，表示与$S_i$最接近信息的最长公共前缀的长度。

样例输入输出

3
abc
ab
bc

2
2
0​