Little Cyan Fish は文字列理論がとても好きです。今日、Little Cyan Fish はあなたを誘って、人間のニックネームの研究を一緒に続けようとしています。
Little Cyan Fish の宇宙では、人間のニックネームは英小文字（a から z）のみからなる文字列として表すことができます。例えば、「qingyu」や「xiuga」は人間のニックネームですが、「Abacde」はそうではありません。
Little Cyan Fish は、名前 $s$ が $s$ のすべての真接尾辞$^\dagger$ $t$ よりも辞書順で小さい$^*$とき、かつそのときに限り、$s$ を Lyndon 文字列であるとみなします。例えば、「abacde」は Lyndon 文字列ですが、「qingyu」は Lyndon 文字列ではありません（なぜなら、その真接尾辞「ingyu」よりも辞書順で小さくないからです）。
今、Little Cyan Fish は長さ $n$ の人間のニックネーム $s$ をあなたに与えます。1 回の操作では、1 つの位置を選び、その位置の文字を任意の英小文字に置き換えることができます。$s$ を Lyndon 文字列にするために必要な最小の操作回数を求めてください。
$^*$ ある文字列が別の文字列よりも辞書順で小さいとは、その文字列がもう一方の文字列の真接頭辞であるか、あるいは 2 つの文字列が最初に異なる位置における文字がアルファベット順でより前に現れることをいいます。
$^\dagger$ 真接尾辞とは、元の文字列と等しくない空でない接尾辞のことです。例えば、「qqoj」には $3$ 個の真接尾辞があり、それらは「j」、「oj」、「qoj」です。
入力
複数のテストケースが与えられます。入力の最初の行には、テストケースの個数を表す単一の整数 $T$（$1 \le T \le 10^4$）が含まれます。
各テストケースについて、最初の行には単一の整数 $n$（$1 \le n \le 3000$）が含まれます。2 行目には英小文字のみからなる長さ $n$ の文字列 $s$ が含まれます。
すべてのテストケースにわたる $n^2$ の総和は $9 \times 10^6$ を超えないことが保証されます。
出力
各テストケースについて、$s$ を Lyndon 文字列にするために必要な最小の操作回数を表す単一の整数を 1 行に出力してください。
入出力例
入力 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
出力 1
0 1 2 3
注記
1 番目のサンプルテストケースでは、文字列はすでに Lyndon 文字列であるため、操作は必要ありません。
2 番目のサンプルテストケースでは、Little Cyan Fish は最後の文字を b に変更して aaab を得ることができます。
3 番目のサンプルテストケースでは、最初の文字と最後の文字をそれぞれ a と c に変更して abac を得ることができます。1 回の操作では不十分です。
4 番目のサンプルテストケースでは、最初の 2 文字を a に、最後の文字を b に変更して aaaab を得ることができます。3 回未満の操作でこれを達成することは不可能です。