Little Cyan Fish bardzo lubi teorię słów. Dzisiaj Little Cyan Fish zaprasza cię do kontynuowania wspólnych badań nad ludzkimi pseudonimami.
We wszechświecie Little Cyan Fish ludzki pseudonim można przedstawić jako napis składający się wyłącznie z małych liter alfabetu łacińskiego (od a do z). Na przykład „qingyu” oraz „xiuga” są ludzkimi pseudonimami, ale „Abacde” nim nie jest.
Little Cyan Fish uważa nazwę $s$ za słowo Lyndona wtedy i tylko wtedy, gdy $s$ jest mniejsze leksykograficznie$^*$ od każdego właściwego sufiksu$^\dagger$ $t$ napisu $s$. Na przykład „abacde” jest słowem Lyndona, ale „qingyu” nie jest słowem Lyndona (ponieważ nie jest mniejsze leksykograficznie od swojego właściwego sufiksu „ingyu”).
Teraz Little Cyan Fish daje ci ludzki pseudonim $s$ o długości $n$. W jednej operacji możesz wybrać jedną pozycję i zastąpić znajdujący się na niej znak dowolną małą literą alfabetu łacińskiego. Znajdź minimalną liczbę operacji potrzebnych, aby przekształcić $s$ w słowo Lyndona.
$^*$ Napis jest mniejszy leksykograficznie od innego napisu, jeśli jest właściwym prefiksem tego drugiego napisu lub jeśli jego znak na pierwszej pozycji, na której napisy się różnią, występuje wcześniej w alfabecie.
$^\dagger$ Właściwy sufiks to niepusty sufiks, który nie jest równy oryginalnemu napisowi. Na przykład „qqoj” ma $3$ właściwe sufiksy: „j”, „oj” oraz „qoj”.
Wejście
Test składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 3000$). Drugi wiersz zawiera napis $s$ o długości $n$, składający się wyłącznie z małych liter alfabetu łacińskiego.
Gwarantowane jest, że suma wartości $n^2$ po wszystkich przypadkach testowych nie przekracza $9 \times 10^6$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający jedną liczbę całkowitą, oznaczającą minimalną liczbę operacji potrzebnych, aby przekształcić $s$ w słowo Lyndona.
Przykład
Wejście 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Wyjście 1
0 1 2 3
Uwagi
W pierwszym przykładowym przypadku testowym napis jest już słowem Lyndona, więc żadna operacja nie jest potrzebna.
W drugim przykładowym przypadku testowym Little Cyan Fish może zmienić ostatni znak na b, otrzymując aaab.
W trzecim przykładowym przypadku testowym może zmienić pierwszy i ostatni znak odpowiednio na a i c, otrzymując abac. Jedna operacja nie wystarczy.
W czwartym przykładowym przypadku testowym może zmienić dwa pierwsze znaki na a, a ostatni znak na b, otrzymując aaaab. Nie da się tego osiągnąć w mniej niż trzech operacjach.