小青魚好鍾意字串理論。今日，小青魚邀請你繼續同佢一齊研究人類嘅暱稱。
喺小青魚嘅宇宙入面，一個人類暱稱可以表示做一個淨係由細楷拉丁字母（a 到 z）組成嘅字串。例如，「qingyu」同埋「xiuga」係人類暱稱，但係「Abacde」就唔係。
小青魚認為一個名 $s$ 係 Lyndon 串，當且僅當 $s$ 嘅字典序細過$^*$ $s$ 嘅每一個真後綴$^\dagger$ $t$。例如，「abacde」係 Lyndon 串，但係「qingyu」唔係 Lyndon 串（因為佢嘅字典序並唔細過佢嘅真後綴「ingyu」）。
而家，小青魚畀你一個長度係 $n$ 嘅人類暱稱 $s$。喺一次操作入面，你可以揀一個位置，然後將嗰度嘅字元換成任何一個細楷拉丁字母。請你搵出將 $s$ 變成 Lyndon 串最少需要幾多次操作。
$^*$ 如果一個字串係另一個字串嘅真前綴，或者喺兩個字串第一個唔同嘅位置上面，呢個字串嘅字元喺字母表入面出現得更加早，噉就話呢個字串嘅字典序細過另一個字串。
$^\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$ 變成 Lyndon 串最少需要嘅操作次數。
範例
輸入格式 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
輸出格式 1
0 1 2 3
說明
喺第一組範例測試數據入面，呢個字串已經係 Lyndon 串，所以唔需要做任何操作。
喺第二組範例測試數據入面，小青魚可以將最後一個字元改成 b，得到 aaab。
喺第三組範例測試數據入面，佢可以將第一個字元同最後一個字元分別改成 a 同 c，得到 abac。淨係做一次操作係唔夠嘅。
喺第四組範例測試數據入面，佢可以將頭兩個字元改成 a，再將最後一個字元改成 b，得到 aaaab。冇可能用少過三次操作達到目標。