給定一個由小寫英文字母組成的字串 $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$。