Little Cyan Fish sangat menyukai teori string. Hari ini, Little Cyan Fish mengundang Anda untuk mempelajari nama panggilan manusia bersamanya.

Di alam semesta Little Cyan Fish, semua nama panggilan manusia dapat direpresentasikan sebagai sebuah string yang hanya berisi huruf Latin kecil (a sampai z). Sebagai contoh, "qingyu" dan "xiuga" adalah nama panggilan manusia, tetapi "Abacde" bukanlah nama panggilan manusia.

Little Cyan Fish menganggap sebuah nama $s$ bersifat Lyndon jika dan hanya jika untuk setiap sufiks sejati* $t$ dari $s$, urutan leksikografis dari $s$ lebih kecil secara tegas daripada $t$. Sebagai contoh, "abacde" adalah string Lyndon, tetapi "qingyu" bukanlah string Lyndon (karena string aslinya tidak lebih kecil secara leksikografis daripada sufiks sejati "ingyu").

Sekarang, Little Cyan Fish memberikan sebuah nama panggilan manusia $s$ kepada Anda, dan Anda perlu menghitung berapa banyak pasangan berbeda $(l, r)$ dengan $1 \le l \le r \le |s|$ sedemikian sehingga $s[l \dots r]$ bersifat Lyndon.

* Sufiks sejati adalah sufiks tak kosong yang tidak sama dengan string aslinya. Sebagai contoh, "qqoj" memiliki $3$ sufiks sejati, yaitu "j", "oj", dan "qoj".

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat tunggal $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, masukan berisi satu baris dengan sebuah string $s$ ($1 \le |s| \le 2 \times 10^5$), yang menyatakan nama panggilan manusia.

Dijamin bahwa jumlah $|s|$ di semua kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi satu bilangan bulat, yang menyatakan jawabannya.

Contoh

Masukan 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

Keluaran 1

3
9
27
16
58
32