דג ציאן הקטן (Little Cyan Fish) אוהב מאוד את תורת המחרוזות. היום, דג ציאן הקטן מזמין אותך לחקור איתו כינויים אנושיים.

ביקום של דג ציאן הקטן, ניתן לייצג את כל הכינויים האנושיים כמחרוזת המכילה אך ורק אותיות לטיניות קטנות (a עד z). לדוגמה, "qingyu" ו-"xiuga" הם כינויים אנושיים, אך "Abacde" אינו כינוי אנושי.

דג ציאן הקטן מחשיב שם $s$ כ-Lyndon אם ורק אם עבור כל סיפא ממש* $t$ של $s$, הסדר הלקסיקוגרפי של $s$ קטן ממש מזה של $t$. לדוגמה, "abacde" היא מחרוזת Lyndon, אך "qingyu" אינה מחרוזת Lyndon (מכיוון שהמחרוזת המקורית אינה קטנה לקסיקוגרפית מהסיפא ממש "ingyu").

כעת, דג ציאן הקטן נותן לך כינוי אנושי $s$, ועליך לחשב כמה זוגות שונים $(l, r)$ עם $1 \le l \le r \le |s|$ קיימים כך ש-$s[l \dots r]$ היא מחרוזת Lyndon.

* סיפא ממש (proper suffix) היא סיפא לא-ריקה שאינה שווה למחרוזת המקורית. לדוגמה, ל-"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