Little Cyan Fish жолдар теориясын өте жақсы көреді. Бүгін Little Cyan Fish сізді өзімен бірге адам лақап аттарын зерттеуді жалғастыруға шақырады.
Little Cyan Fish әлемінде адамның лақап атын тек кіші латын әріптерінен (a-дан z-ке дейін) тұратын жол ретінде көрсетуге болады. Мысалы, “qingyu” және “xiuga” — адам лақап аттары, бірақ “Abacde” олай емес.
Little Cyan Fish $s$ атауын тек сонда ғана Линдон жолы деп есептейді, егер $s$ лексикографиялық тұрғыдан $s$ жолының кез келген меншікті суффиксінен$^\dagger$ $t$ кіші$^*$ болса. Мысалы, “abacde” — Линдон жолы, бірақ “qingyu” Линдон жолы емес (себебі ол өзінің “ingyu” меншікті суффиксінен лексикографиялық тұрғыдан кіші емес).
Енді Little Cyan Fish сізге ұзындығы $n$ болатын $s$ адам лақап атын береді. Бір амалда сіз бір орынды таңдап, ондағы таңбаны кез келген кіші латын әрпіне ауыстыра аласыз. $s$ жолын Линдон жолына айналдыру үшін қажетті ең аз амалдар санын табыңыз.
$^*$ Егер бір жол екінші жолдың меншікті префиксі болса немесе екі жол ерекшеленетін бірінші орындағы оның таңбасы әліпбиде ертерек кездессе, онда ол жол екінші жолдан лексикографиялық тұрғыдан кіші болады.
$^\dagger$ Меншікті суффикс дегеніміз — бастапқы жолға тең емес бос емес суффикс. Мысалы, “qqoj” жолының $3$ меншікті суффиксі бар, олар: “j”, “oj” және “qoj”.
Кіріс деректер
Бірнеше тест жиынтығы бар. Кіріс деректердің бірінші жолында тест жиынтықтарының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^4$) берілген.
Әрбір тест жиынтығы үшін бірінші жолда бір бүтін сан $n$ ($1 \le n \le 3000$) берілген. Екінші жолда тек кіші латын әріптерінен тұратын, ұзындығы $n$ болатын $s$ жолы берілген.
Барлық тест жиынтықтары бойынша $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 жолын ала алады. Бұған үш амалдан аз амалмен қол жеткізу мүмкін емес.