يحب 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. من المستحيل تحقيق ذلك في أقل من ثلاث عمليات.