A Little Cyan Fish piace molto la teoria delle stringhe. Oggi, Little Cyan Fish ti invita a studiare i soprannomi umani insieme a lui.

Nell'universo di Little Cyan Fish, tutti i soprannomi umani possono essere rappresentati come una stringa contenente solo lettere latine minuscole (a fino a z). Ad esempio, "qingyu" e "xiuga" sono soprannomi umani, ma "Abacde" non è un soprannome umano.

Little Cyan Fish considera un nome $s$ di Lyndon se e solo se per ogni suffisso proprio* $t$ di $s$, l'ordine lessicografico di $s$ è strettamente minore di $t$. Ad esempio, "abacde" è una stringa di Lyndon, ma "qingyu" non è una stringa di Lyndon (perché la stringa originale non è lessicograficamente minore del suffisso proprio "ingyu").

Ora, Little Cyan Fish ti dà un soprannome umano $s$, e devi calcolare quante coppie diverse $(l, r)$ con $1 \le l \le r \le |s|$ esistono tali che $s[l \dots r]$ sia di Lyndon.

* Un suffisso proprio è un suffisso non vuoto che non è uguale alla stringa originale. Ad esempio, "qqoj" ha $3$ suffissi propri, che sono "j", "oj" e "qoj".

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ogni caso di test, l'input contiene una singola riga con una stringa $s$ ($1 \le |s| \le 2 \times 10^5$), che indica il soprannome umano.

È garantito che la somma di $|s|$ su tutti i casi di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa una singola riga contenente un intero, che indica la risposta.

Esempio

Input 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Output 1

3
9
27
16
58
32