Little Cyan Fish mag die Theorie der Zeichenketten sehr. Heute lädt Little Cyan Fish dich ein, gemeinsam mit ihm menschliche Spitznamen weiter zu untersuchen.

Im Universum von Little Cyan Fish kann ein menschlicher Spitzname als eine Zeichenkette dargestellt werden, die ausschließlich aus lateinischen Kleinbuchstaben (a bis z) besteht. Beispielsweise sind „qingyu“ und „xiuga“ menschliche Spitznamen, „Abacde“ jedoch nicht.

Little Cyan Fish betrachtet einen Namen $s$ genau dann als ein Lyndon-Wort, wenn $s$ lexikographisch kleiner$^*$ ist als jedes echte Suffix$^\dagger$ $t$ von $s$. Beispielsweise ist „abacde“ ein Lyndon-Wort, aber „qingyu“ ist kein Lyndon-Wort (da es nicht lexikographisch kleiner als sein echtes Suffix „ingyu“ ist).

Nun gibt dir Little Cyan Fish einen menschlichen Spitznamen $s$ der Länge $n$. In einer Operation kannst du eine Position auswählen und das dortige Zeichen durch einen beliebigen lateinischen Kleinbuchstaben ersetzen. Bestimme die minimale Anzahl an Operationen, die nötig sind, um $s$ in ein Lyndon-Wort umzuwandeln.

$^*$ Eine Zeichenkette ist lexikographisch kleiner als eine andere Zeichenkette, wenn sie ein echtes Präfix der anderen Zeichenkette ist oder wenn ihr Zeichen an der ersten Position, an der sich die Zeichenketten unterscheiden, im Alphabet früher vorkommt.

$^\dagger$ Ein echtes Suffix ist ein nicht-leeres Suffix, das nicht gleich der ursprünglichen Zeichenkette ist. Beispielsweise hat „qqoj“ $3$ echte Suffixe, nämlich „j“, „oj“ und „qoj“.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($1 \le n \le 3000$). Die zweite Zeile enthält eine Zeichenkette $s$ der Länge $n$, die ausschließlich aus lateinischen Kleinbuchstaben besteht.

Es wird garantiert, dass die Summe von $n^2$ über alle Testfälle $9 \times 10^6$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die die minimale Anzahl an Operationen angibt, die nötig sind, um $s$ in ein Lyndon-Wort umzuwandeln.

Beispiele

Eingabe 1

4
4
abac
4
aaaa
4
bbaa
5
bbaaa

Ausgabe 1

0
1
2
3

Hinweis

Im ersten Beispiel-Testfall ist die Zeichenkette bereits ein Lyndon-Wort, sodass keine Operation erforderlich ist.

Im zweiten Beispiel-Testfall kann Little Cyan Fish das letzte Zeichen in b ändern und erhält so aaab.

Im dritten Beispiel-Testfall kann er das erste und das letzte Zeichen in a bzw. c ändern und erhält so abac. Eine einzige Operation reicht nicht aus.

Im vierten Beispiel-Testfall kann er die ersten beiden Zeichen in a und das letzte Zeichen in b ändern und erhält so aaaab. Es ist unmöglich, dies in weniger als drei Operationen zu erreichen.