Кішкентай Көгілдір Балық (Little Cyan Fish) жолдар теориясын өте жақсы көреді. Бүгін Кішкентай Көгілдір Балық сізді өзімен бірге адамдардың лақап аттарын зерттеуге шақырады.

Кішкентай Көгілдір Балықтың әлемінде адамдардың барлық лақап аттарын тек кіші латын әріптерінен (a-дан z-ке дейін) тұратын жол ретінде көрсетуге болады. Мысалы, "qingyu", "xiuga" — адам лақап аттары, бірақ "Abacde" — адам лақап аты емес.

Кішкентай Көгілдір Балық $s$ есімін тек сонда ғана Lyndon жолы деп есептейді, егер $s$ жолының әрбір меншікті суффиксі* $t$ үшін $s$-тің лексикографиялық реті $t$-дан қатаң кіші болса. Мысалы, "abacde" — Lyndon жолы, бірақ "qingyu" Lyndon жолы емес (себебі бастапқы жол өзінің "ingyu" меншікті суффиксінен лексикографиялық тұрғыдан кіші емес).

Енді Кішкентай Көгілдір Балық сізге адамның лақап аты $s$-ті береді, сізге $1 \le l \le r \le |s|$ болатындай және $s[l \dots r]$ Lyndon жолы болатындай қанша әртүрлі $(l, 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