Маленькая Циановая Рыбка очень любит теорию строк. Сегодня Маленькая Циановая Рыбка приглашает вас вместе с ней изучать человеческие никнеймы.

Во вселенной Маленькой Циановой Рыбки все человеческие никнеймы можно представить в виде строки, содержащей только строчные латинские буквы (от a до z). Например, "qingyu", "xiuga" являются человеческими никнеймами, а "Abacde" человеческим никнеймом не является.

Маленькая Циановая Рыбка считает имя $s$ строкой Линдона тогда и только тогда, когда для каждого собственного суффикса* $t$ строки $s$ строка $s$ лексикографически строго меньше $t$. Например, "abacde" — это строка Линдона, а "qingyu" — нет (потому что исходная строка лексикографически не меньше собственного суффикса "ingyu").

Теперь Маленькая Циановая Рыбка даёт вам человеческий никнейм $s$, и вам нужно вычислить, сколько существует различных пар $(l, r)$ ($1 \le l \le r \le |s|$), таких что подстрока $s[l \dots r]$ является строкой Линдона.

* Собственный суффикс — это непустой суффикс, не совпадающий со всей исходной строкой. Например, у строки "qqoj" есть $3$ собственных суффикса: "j", "oj" и "qoj".

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит одно целое число $T$ ($1 \le T$) — количество наборов входных данных.

Для каждого набора входных данных дана одна строка, содержащая строку $s$ ($1 \le |s| \le 2 \times 10^5$) — человеческий никнейм.

Гарантируется, что сумма $|s|$ по всем наборам входных данных не превосходит $2 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую одно целое число — ответ на задачу.

Пример

Входные данные 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Выходные данные 1

3
9
27
16
58
32