题目描述

对于字符串 $s$ 求 $∑_p cnt(s,p)^2$。其中 $cnt(s,p)$ 表示子串 $p$ 在 $s$ 中的出现次数。

输入格式

第一行一个整数 $T$，表示数据组数，$T\le 10$。

接下来 $T$ 行，每行一个字符串 $s$，长度不超过 $10^5$，仅包含小写字母。

输出格式

对于每个字符串，在一行中输出一个整数表示答案。

4
aa
abcd
ccc
abcc

5
10
14
12