Дана строка $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.