Little Cyan Fish אוהב מאוד את תורת המחרוזות. היום, Little Cyan Fish מזמין אתכם להמשיך ולחקור איתו כינויים אנושיים.
ביקום של Little Cyan Fish, כינוי אנושי יכול להיות מיוצג כמחרוזת המורכבת רק מאותיות לטיניות קטנות (a עד z). לדוגמה, “qingyu” ו-“xiuga” הם כינויים אנושיים, אך “Abacde” אינו כזה.
Little Cyan Fish מחשיב שם $s$ כמחרוזת לינדון אם ורק אם $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. אי אפשר להשיג זאת בפחות משלוש פעולות.