אם אפשר לפצל מחרוזת לצורה $AABB$, כאשר $A,B$ הן מחרוזות לא ריקות כלשהן, נקרא לפיצול זה פיצול מצוין.

לדוגמה, עבור המחרוזת aabaabaa, אם נבחר $A=\mathtt{aab}$, $B=\mathtt{a}$, נקבל דרך אחת לפצל את המחרוזת לצורה $AABB$.

ייתכן שלמחרוזת אין פיצול מצוין, וייתכן שיש לה יותר מאחד. לדוגמה, גם הבחירה $A=\mathtt{a}$, $B=\mathtt{baa}$ מייצגת את המחרוזת שלעיל בצורה $AABB$; לעומת זאת, למחרוזת abaabaa אין פיצול מצוין.

כעת נתונה מחרוזת $S$ באורך $n$. עלינו למצוא את המספר הכולל של הפיצולים המצוינים, על פני כל הפיצולים של כל תתי־המחרוזות שלה. תת־מחרוזת כאן היא קטע רציף של מחרוזת.

שימו לב לנקודות הבאות:

1. תתי־מחרוזות זהות המופיעות במקומות שונים נחשבות לתתי־מחרוזות שונות, והפיצולים המצוינים של כל אחת מהן נספרים בתשובה.
2. בפיצול מותר ש־$A=B$. לדוגמה, למחרוזת cccc יש הפיצול $A=B=\mathtt{c}$.
3. המחרוזת עצמה היא גם תת־מחרוזת שלה.

קלט

קובץ הקלט הוא excellent.in.

כל קובץ קלט מכיל כמה מקרי בדיקה. השורה הראשונה מכילה מספר שלם אחד בלבד, $T$, מספר המקרים. מובטח ש־$1\le T\le10$.

כל אחת מ־$T$ השורות הבאות מכילה מחרוזת $S$ המורכבת מאותיות אנגליות קטנות בלבד, כמתואר בשאלה.

פלט

קובץ הפלט הוא excellent.out.

הדפיסו $T$ שורות, בכל אחת מספר שלם אחד: כמה מבין כל הפיצולים של כל תתי־המחרוזות של $S$ הם פיצולים מצוינים.

דוגמאות

קלט 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

פלט 1

3
5
4
7

הסבר

נסמן ב־$S[i,j]$ את תת־המחרוזת של $S$ מהתו ה־$i$ עד התו ה־$j$, כשהספירה מתחילה ב־$1$.

במקרה הראשון, לשלוש תתי־מחרוזות יש פיצול מצוין:

$S[1,4]=\mathtt{aabb}$, עם הפיצול המצוין $A=\mathtt{a}$, $B=\mathtt{b}$.

$S[3,6]=\mathtt{bbbb}$, עם הפיצול המצוין $A=\mathtt{b}$, $B=\mathtt{b}$.

$S[1,6]=\mathtt{aabbbb}$, עם הפיצול המצוין $A=\mathtt{a}$, $B=\mathtt{bb}$.

לשאר תתי־המחרוזות אין פיצול מצוין, ולכן התשובה במקרה הראשון היא $3$.

במקרה השני יש שתי קבוצות, הכוללות ארבע תתי־מחרוזות בעלות פיצול מצוין:

עבור $S[1,4]=S[2,5]=S[3,6]=\mathtt{cccc}$, הפיצול המצוין זהה: $A=\mathtt{c}$, $B=\mathtt{c}$. אך מכיוון שתתי־המחרוזות נמצאות במקומות שונים, יש לספור אותו שלוש פעמים.

עבור $S[1,6]=\mathtt{cccccc}$, יש שני פיצולים מצוינים: $A=\mathtt{c}$, $B=\mathtt{cc}$, וכן $A=\mathtt{cc}$, $B=\mathtt{c}$. אלה פיצולים שונים של אותה תת־מחרוזת, וגם שניהם נספרים בתשובה.

לכן התשובה במקרה השני היא $3+2=5$.

במקרה השלישי, לכל אחת מתתי־המחרוזות $S[1,8]$, $S[4,11]$ יש שני פיצולים מצוינים. $S[1,8]$ היא הדוגמה המופיעה בתיאור השאלה, ולכן התשובה היא $2+2=4$.

במקרה הרביעי, לכל אחת מתתי־המחרוזות $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ יש פיצול מצוין אחד. ל־$S[3,14]$ יש שני פיצולים מצוינים, ולכן התשובה היא $5+2=7$.

דוגמה 2

ראו את הקבצים excellent/excellent2.in ו־excellent/excellent2.ans בתיקיית המתחרה.

דוגמה 3

ראו את הקבצים excellent/excellent3.in ו־excellent/excellent3.ans בתיקיית המתחרה.

תתי־משימות

בכל קבוצות הבדיקה מובטח ש־$1\le T\le10$. המגבלות הבאות חלות על מקרה קלט אחד; כלומר, כל $T$ המקרים באותה קבוצת בדיקה מקיימים את המגבלות.

נסמן ב־$n$ את אורך המחרוזת $S$. המגבלות המדויקות לכל קבוצת בדיקה מופיעות בטבלה הבאה: