给定一个由小写英文字母组成的字符串 $s$。

考虑一个区间 $[\ell, r]$，满足 $2 \le \ell \le r \le |s|$。定义 $f(\ell, r)$ 为子串 $s[1, \ell - 1]$ 的最长后缀的长度，且该后缀可以被划分为若干个子串 $s[\ell, r]$ 的前缀。如果不存在这样的后缀，则 $f(\ell, r) = 0$。

求和 $\sum_{\ell=2}^{|s|} \sum_{r=\ell}^{|s|} f(\ell, r)$。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例仅包含一行，为一个由小写英文字母组成的字符串 $s$ ($2 \le |s| \le 2 \cdot 10^5$)。

保证所有测试用例的 $|s|$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示问题的答案。

样例

输入格式 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

输出格式 1

1
0
6
7
0
74
51
20

说明

考虑第三个测试用例。在这种情况下，$f(2, 2) = 0, f(2, 3) = 0, f(2, 4) = 0, f(2, 5) = 0, f(3, 3) = 0, f(3, 4) = 2, f(3, 5) = 2, f(4, 4) = 0, f(4, 5) = 2, f(5, 5) = 0$。因此答案为 $6$。