小文字の英字からなる文字列 $s$ が与えられます。

$2 \le \ell \le r \le |s|$ を満たす区間 $[\ell, r]$ を考えます。部分文字列 $s[1, \ell - 1]$ の接尾辞のうち、部分文字列 $s[\ell, r]$ の接頭辞をいくつか連結することで構成できるもののうち、最長のものの長さを $f(\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

注記

3番目のテストケースを考えます。この場合、$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$ です。