A Little Cyan Fish piace moltissimo la teoria delle stringhe. Oggi, Little Cyan Fish ti invita a continuare a studiare i soprannomi umani insieme a lui.
Nell'universo di Little Cyan Fish, un soprannome umano può essere rappresentato come una stringa composta esclusivamente da lettere latine minuscole (da a a z). Ad esempio, “qingyu” e “xiuga” sono soprannomi umani, mentre “Abacde” non lo è.
Little Cyan Fish considera un nome $s$ una stringa di Lyndon se e solo se $s$ è lessicograficamente minore$^*$ di ogni suffisso proprio$^\dagger$ $t$ di $s$. Ad esempio, “abacde” è una stringa di Lyndon, ma “qingyu” non è una stringa di Lyndon (perché non è lessicograficamente minore del suo suffisso proprio “ingyu”).
Ora, Little Cyan Fish ti dà un soprannome umano $s$ di lunghezza $n$. In un'operazione, puoi scegliere una posizione e sostituire il suo carattere con qualsiasi lettera latina minuscola. Trova il numero minimo di operazioni necessarie per rendere $s$ una stringa di Lyndon.
$^*$ Una stringa è lessicograficamente minore di un'altra stringa se è un prefisso proprio dell'altra stringa, oppure se il suo carattere nella prima posizione in cui le stringhe differiscono precede l'altro nell'alfabeto.
$^\dagger$ Un suffisso proprio è un suffisso non vuoto che non è uguale alla stringa originale. Ad esempio, “qqoj” ha $3$ suffissi propri, che sono “j”, “oj” e “qoj”.
Input
Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T \le 10^4$), che indica il numero di casi di test.
Per ciascun caso di test, la prima riga contiene un singolo intero $n$ ($1 \le n \le 3000$). La seconda riga contiene una stringa $s$ di lunghezza $n$, composta esclusivamente da lettere latine minuscole.
È garantito che la somma di $n^2$ su tutti i casi di test non superi $9 \times 10^6$.
Output
Per ciascun caso di test, stampa una singola riga contenente un singolo intero, che indica il numero minimo di operazioni necessarie per rendere $s$ una stringa di Lyndon.
Esempi
Input 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Output 1
0 1 2 3
Note
Nel primo caso di test di esempio, la stringa è già una stringa di Lyndon, quindi non è necessaria alcuna operazione.
Nel secondo caso di test di esempio, Little Cyan Fish può cambiare l'ultimo carattere in b, ottenendo aaab.
Nel terzo caso di test di esempio, può cambiare il primo e l'ultimo carattere in a e c, rispettivamente, ottenendo abac. Una sola operazione non è sufficiente.
Nel quarto caso di test di esempio, può cambiare i primi due caratteri in a e l'ultimo carattere in b, ottenendo aaaab. È impossibile ottenere questo risultato in meno di tre operazioni.