小青魚非常喜歡字串理論。今天，小青魚邀請你繼續和他一起研究人類的暱稱。
在小青魚的宇宙中，一個人類暱稱可以表示為一個僅由小寫拉丁字母（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。無法用少於三次操作達成目標。