和人类一样，奶牛也常常希望自己能在某些方面显得与众不同。由于农夫约翰的奶牛都属于同一个品种，长相也非常相似，因此它们想要通过名字来衡量自己的独特性。

每头奶牛的名字都有若干个子串。例如，“amy”的子串有 {a, m, y, am, my, amy}，而“tommy”的子串有 {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}。

奶牛名字的“独特性因子”定义为该名字中不被其他任何奶牛名字所包含的子串数量。例如，如果 amy 单独在一个牛群中，她的独特性因子就是 6。如果 tommy 单独在一个牛群中，他的独特性因子就是 14。然而，如果它们在一起，amy 的独特性因子就会变为 3，而 tommy 的独特性因子则变为 11。

给定一个牛群，请确定每头奶牛的独特性因子。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^5$)。接下来的 $N$ 行，每行包含一头奶牛的名字。每个名字仅包含小写字母 a-z。所有名字的总长度不超过 $10^5$。

输出格式

输出 $N$ 个数字，每行一个，分别描述每头奶牛的独特性因子。

样例

输入格式 1

3
amy
tommy
bessie

输出格式 1

3
11
19