题目描述

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成的串。例如，字符串 aaab 有非空子 a,b,aa,ab,aaa,aab,aaab，一共 7 个。

注意在计算时，只算本质不同的串的个数。

请问，字符串 S 有多少个不同的非空子串？

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 1 个字符串 $S$。

输出描述

对每个输入输出一个整数表示答案。

3
aaab
aaaaa
abaabbaaababaaab

7
5
100

评测用例规模与约定：

对于所有评测用例，$1≤T≤10,1≤|S|≤1000$，绝对值符号代表长度，字符串只由小写字母组成。