Little Cyan Fish ชอบทฤษฎีสตริงเป็นอย่างมาก วันนี้ Little Cyan Fish จึงชวนคุณมาศึกษาชื่อเล่นของมนุษย์ร่วมกับเขา

ในจักรวาลของ Little Cyan Fish ชื่อเล่นของมนุษย์ทั้งหมดสามารถแทนได้ด้วยสตริงที่ประกอบด้วยตัวอักษรละตินพิมพ์เล็กเท่านั้น (a ถึง z) ตัวอย่างเช่น "qingyu", "xiuga" เป็นชื่อเล่นของมนุษย์ แต่ "Abacde" ไม่ใช่ชื่อเล่นของมนุษย์

Little Cyan Fish ถือว่าชื่อ $s$ เป็น Lyndon ก็ต่อเมื่อสำหรับทุกส่วนท้ายแท้* $t$ ของ $s$ ลำดับพจนานุกรมของ $s$ มีค่าน้อยกว่า $t$ อย่างแท้จริง ตัวอย่างเช่น "abacde" เป็นสตริง Lyndon แต่ "qingyu" ไม่ใช่สตริง Lyndon (เนื่องจากสตริงตั้งต้นไม่ได้มีลำดับพจนานุกรมน้อยกว่าส่วนท้ายแท้ "ingyu")

ตอนนี้ Little Cyan Fish ให้ชื่อเล่นของมนุษย์ $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