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

У всесвіті Маленької Ціанової Рибки всі людські нікнейми можна подати у вигляді рядка, що містить лише малі латинські літери (від 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