A Little Cyan Fish le gusta mucho la teoría de cadenas. Hoy, Little Cyan Fish te invita a estudiar apodos humanos con él.

En el universo de Little Cyan Fish, todos los apodos humanos pueden representarse como una cadena que contiene únicamente letras latinas minúsculas (a a z). Por ejemplo, "qingyu" y "xiuga" son apodos humanos, pero "Abacde" no es un apodo humano.

Little Cyan Fish considera que un nombre $s$ es de Lyndon si y solo si para cada sufijo propio* $t$ de $s$, el orden lexicográfico de $s$ es estrictamente menor que el de $t$. Por ejemplo, "abacde" es una cadena de Lyndon, pero "qingyu" no es una cadena de Lyndon (porque la cadena original no es lexicográficamente menor que el sufijo propio "ingyu").

Ahora, Little Cyan Fish te da un apodo humano $s$, y debes calcular cuántos pares diferentes $(l, r)$ con $1 \le l \le r \le |s|$ existen tales que $s[l \dots r]$ sea de Lyndon.

* Un sufijo propio es un sufijo no vacío que no es igual a la cadena original. Por ejemplo, "qqoj" tiene $3$ sufijos propios, que son "j", "oj" y "qoj".

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la entrada contiene una sola línea con una cadena $s$ ($1 \le |s| \le 2 \times 10^5$), que indica el apodo humano.

Se garantiza que la suma de $|s|$ en todos los casos de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea que contenga un entero, indicando la respuesta.

Ejemplo

Entrada 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Salida 1

3
9
27
16
58
32