[AdditionalFile2388.zip](file://AdditionalFile2388.zip?type=additional_file)

#2388. 「USACO 2017.12 Platinum」Standing Out from the Herd

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2017 December Contest, Platinum Problem 1. Standing Out from the Herd

就像人类一样，奶牛通常喜欢与众不同。因为农夫 John 的奶牛都是同一个品种的，看起来也很相似，所以它们想要确定它们名字的不同之处。

每头奶牛的名字都有一些数量的子串。例如，$\texttt{amy}$ 的子串有 $\texttt{\{a, m, y, am, my, amy\}}$，$\texttt{tommy}$ 的子串有 $\texttt{\{t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy\}}$。

一头奶牛的名字有一个「不同因子」，这个值表示这个名字独有的子串数量。例如，如果牛群中只有 $\texttt{amy}$ 自己一头牛，那么她的不同因子就是 $6$。如果牛群中只有 $\texttt{tommy}$ 自己一头牛，那么他的不同因子就是 $14$。但如果他们同在一个牛群的话，$\texttt{amy}$ 的不同因子就会变成 $3$，$\texttt{tommy}$ 的不同因子就会变成 $11$。

给定牛群的信息，请确定每头牛的不同因子。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含牛群中一头牛的名字。每个名字只包含小写英文字母 a 到 z。

输出格式

输出 $N$ 行，每行一个整数，表示每头牛的不同因子。

样例

输入

3
amy
tommy
bessie

输出

3
11
19

数据范围及提示

$1\le N\le 10^5$，保证所有奶牛的名字长度之和不超过 $10^5$。