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

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

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

ตอนนี้ Little Cyan Fish ให้ชื่อเล่นของมนุษย์ $s$ ที่มีความยาว $n$ แก่คุณ ในหนึ่งการดำเนินการ คุณสามารถเลือกหนึ่งตำแหน่งแล้วแทนที่อักขระในตำแหน่งนั้นด้วยตัวอักษรละตินพิมพ์เล็กใดก็ได้ จงหาจำนวนการดำเนินการที่น้อยที่สุดที่ต้องใช้เพื่อทำให้ $s$ เป็นสตริงลินดอน

$^*$ สตริงหนึ่งจะมีค่าน้อยกว่าอีกสตริงหนึ่งตามลำดับพจนานุกรม หากมันเป็นส่วนนำแท้ของอีกสตริงหนึ่ง หรือหากอักขระของมันในตำแหน่งแรกที่ทั้งสองสตริงแตกต่างกันมาก่อนในลำดับตัวอักษร

$^\dagger$ ส่วนท้ายแท้คือส่วนท้ายที่ไม่ว่างและไม่เท่ากับสตริงเดิม ตัวอย่างเช่น “qqoj” มีส่วนท้ายแท้ $3$ ตัว ได้แก่ “j”, “oj” และ “qoj”

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

มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งตัว $T$ ($1 \le T \le 10^4$) แทนจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งตัว $n$ ($1 \le n \le 3000$) บรรทัดที่สองประกอบด้วยสตริง $s$ ที่มีความยาว $n$ ซึ่งประกอบด้วยตัวอักษรละตินพิมพ์เล็กเท่านั้น

รับประกันว่าผลรวมของ $n^2$ จากทุกกรณีทดสอบจะไม่เกิน $9 \times 10^6$

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

สำหรับแต่ละกรณีทดสอบ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัว แทนจำนวนการดำเนินการที่น้อยที่สุดที่ต้องใช้เพื่อทำให้ $s$ เป็นสตริงลินดอน

ตัวอย่าง

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

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

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

0
1
2
3

หมายเหตุ

ในกรณีทดสอบตัวอย่างแรก สตริงนี้เป็นสตริงลินดอนอยู่แล้ว ดังนั้นจึงไม่จำเป็นต้องดำเนินการใดๆ

ในกรณีทดสอบตัวอย่างที่สอง Little Cyan Fish สามารถเปลี่ยนอักขระตัวสุดท้ายเป็น b ทำให้ได้ aaab

ในกรณีทดสอบตัวอย่างที่สาม เขาสามารถเปลี่ยนอักขระตัวแรกและตัวสุดท้ายเป็น a และ c ตามลำดับ ทำให้ได้ abac การดำเนินการเพียงครั้งเดียวไม่เพียงพอ

ในกรณีทดสอบตัวอย่างที่สี่ เขาสามารถเปลี่ยนอักขระสองตัวแรกเป็น a และอักขระตัวสุดท้ายเป็น b ทำให้ได้ aaaab เป็นไปไม่ได้ที่จะทำสำเร็จด้วยจำนวนการดำเนินการที่น้อยกว่าสามครั้ง