หากสตริงหนึ่งสามารถแบ่งเป็นรูป $AABB$ โดย $A$ และ $B$ เป็นสตริงใด ๆ ที่ ไม่ว่าง เราจะเรียกการแบ่งสตริงแบบนี้ว่าเป็นการแบ่งที่ยอดเยี่ยม

ตัวอย่างเช่น สำหรับสตริง aabaabaa หากให้ $A=\texttt{aab}$ และ $B=\texttt{a}$ เราก็พบวิธีหนึ่งในการแบ่งสตริงนี้เป็น $AABB$

สตริงหนึ่งอาจไม่มีการแบ่งที่ยอดเยี่ยม หรืออาจมีการแบ่งที่ยอดเยี่ยมมากกว่าหนึ่งแบบก็ได้ ตัวอย่างเช่น หากให้ $A=\texttt{a}$ และ $B=\texttt{baa}$ ก็สามารถเขียนสตริงข้างต้นเป็น $AABB$ ได้เช่นกัน แต่สตริง abaabaa ไม่มีการแบ่งที่ยอดเยี่ยม

ขณะนี้กำหนดสตริง $S$ ที่มีความยาว $n$ ให้ เราต้องหาจำนวนการแบ่งที่ยอดเยี่ยมทั้งหมด จากวิธีแบ่งทั้งหมดของ สตริงย่อยทุกสตริง ของมัน โดยสตริงย่อยในที่นี้หมายถึงส่วนหนึ่งที่ ต่อเนื่องกัน ของสตริง

มีข้อควรสังเกตดังต่อไปนี้:

1. สตริงย่อยที่เหมือนกันแต่ปรากฏคนละตำแหน่งถือเป็นสตริงย่อยคนละสตริง และการแบ่งที่ยอดเยี่ยมของแต่ละสตริงจะถูกนับในคำตอบ
2. ในการแบ่งหนึ่งครั้ง อนุญาตให้ $A=B$ ได้ ตัวอย่างเช่น cccc มีการแบ่ง $A=B=\texttt{c}$
3. ตัวสตริงเองก็เป็นสตริงย่อยหนึ่งของมันด้วย

ข้อมูลนำเข้า

ไฟล์ข้อมูลนำเข้าคือ excellent.in

ไฟล์ข้อมูลนำเข้าแต่ละไฟล์มีข้อมูลทดสอบหลายชุด บรรทัดแรกของไฟล์มีจำนวนเต็มเพียงหนึ่งจำนวน $T$ แทนจำนวนชุดข้อมูล รับประกันว่า $1\le T\le 10$

จากนั้นมี $T$ บรรทัด แต่ละบรรทัดประกอบด้วยสตริง $S$ ที่มีเฉพาะอักษรภาษาอังกฤษตัวพิมพ์เล็ก โดยมีความหมายตามคำอธิบายโจทย์

ข้อมูลส่งออก

ไฟล์ข้อมูลส่งออกคือ excellent.out

ส่งออก $T$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มหนึ่งจำนวน แทนจำนวนการแบ่งที่ยอดเยี่ยมทั้งหมด ในบรรดาวิธีแบ่งทั้งหมดของสตริงย่อยทุกสตริงของ $S$

ตัวอย่าง

ข้อมูลนำเข้า 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

ข้อมูลส่งออก 1

3
5
4
7

หมายเหตุ

เราใช้ $S[i,j]$ แทนสตริงย่อยของ $S$ ตั้งแต่อักขระที่ $i$ ถึงอักขระที่ $j$ (เริ่มนับจาก $1$)

ในชุดข้อมูลแรก มีสตริงย่อยทั้งหมด 3 สตริงที่มีการแบ่งที่ยอดเยี่ยม:

$S[1,4]=\texttt{aabb}$ มีการแบ่งที่ยอดเยี่ยมเป็น $A=\texttt{a}$, $B=\texttt{b}$

$S[3,6]=\texttt{bbbb}$ มีการแบ่งที่ยอดเยี่ยมเป็น $A=\texttt{b}$, $B=\texttt{b}$

$S[1,6]=\texttt{aabbbb}$ มีการแบ่งที่ยอดเยี่ยมเป็น $A=\texttt{a}$, $B=\texttt{bb}$

สตริงย่อยที่เหลือไม่มีการแบ่งที่ยอดเยี่ยม ดังนั้นคำตอบของชุดข้อมูลแรกคือ $3$

ในชุดข้อมูลที่สอง มีสตริงย่อยที่มีการแบ่งที่ยอดเยี่ยมสองประเภท รวมทั้งหมด 4 สตริง:

สำหรับสตริงย่อย $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ การแบ่งที่ยอดเยี่ยมของทั้งหมดเหมือนกัน คือ $A=\texttt{c}$, $B=\texttt{c}$ แต่เนื่องจากสตริงย่อยเหล่านี้อยู่คนละตำแหน่ง จึงต้องนับ $3$ ครั้ง

สำหรับสตริงย่อย $S[1,6]=\texttt{cccccc}$ มีการแบ่งที่ยอดเยี่ยม $2$ แบบ คือ $A=\texttt{c}$, $B=\texttt{cc}$ และ $A=\texttt{cc}$, $B=\texttt{c}$ ทั้งสองเป็นการแบ่งคนละแบบของสตริงย่อยเดียวกัน จึงต้องนับทั้งหมดในคำตอบ

ดังนั้นคำตอบของชุดข้อมูลที่สองคือ $3+2=5$

ในชุดข้อมูลที่สาม $S[1,8]$ และ $S[4,11]$ ต่างมีการแบ่งที่ยอดเยี่ยม $2$ แบบ โดย $S[1,8]$ คือตัวอย่างในคำอธิบายโจทย์ ดังนั้นคำตอบคือ $2+2=4$

ในชุดข้อมูลที่สี่ $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$, $S[1,8]$ ต่างมีการแบ่งที่ยอดเยี่ยม $1$ แบบ และ $S[3,14]$ มีการแบ่งที่ยอดเยี่ยม $2$ แบบ ดังนั้นคำตอบคือ $5+2=7$

ตัวอย่าง 2

ดู excellent/excellent2.in และ excellent/excellent2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

ตัวอย่าง 3

ดู excellent/excellent3.in และ excellent/excellent3.ans ในไดเรกทอรีของผู้เข้าแข่งขัน

งานย่อย

สำหรับทุกกรณีทดสอบ รับประกันว่า $1\le T\le 10$ ข้อจำกัดของข้อมูลต่อไปนี้ใช้กับข้อมูลนำเข้าหนึ่งชุด กล่าวคือ ข้อมูลทั้ง $T$ ชุดในกรณีทดสอบเดียวกันล้วนเป็นไปตามข้อจำกัด

ให้ $n$ เป็นความยาวของสตริง $S$ ข้อจำกัดโดยละเอียดของแต่ละกรณีทดสอบแสดงในตารางต่อไปนี้: