5989 - NOI：树链剖分：奶牛因子

就像人类一样，奶牛也常常希望在某些方面感到自己与众不同。由于 Farmer John 的奶牛都来自同一品种且外观非常相似，它们希望通过名字来衡量独特性。

每头奶牛的名字都有一些子字符串。例如，"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 个数字，每行一个，表示每头奶牛的独特性因子。