Little Cyan Fish sangat menyukai teori string. Hari ini, Little Cyan Fish mengundang Anda untuk terus mempelajari nama panggilan manusia bersamanya.
Di alam semesta Little Cyan Fish, nama panggilan manusia dapat direpresentasikan sebagai string yang hanya terdiri dari huruf Latin kecil (a hingga z). Sebagai contoh, “qingyu” dan “xiuga” adalah nama panggilan manusia, tetapi “Abacde” bukan.
Little Cyan Fish menganggap sebuah nama $s$ sebagai string Lyndon jika dan hanya jika $s$ lebih kecil secara leksikografis$^*$ daripada setiap sufiks sejati$^\dagger$ $t$ dari $s$. Sebagai contoh, “abacde” adalah string Lyndon, tetapi “qingyu” bukan string Lyndon (karena tidak lebih kecil secara leksikografis daripada sufiks sejatinya “ingyu”).
Sekarang, Little Cyan Fish memberi Anda sebuah nama panggilan manusia $s$ dengan panjang $n$. Dalam satu operasi, Anda dapat memilih satu posisi dan mengganti karakternya dengan huruf Latin kecil apa pun. Carilah jumlah operasi minimum yang diperlukan untuk menjadikan $s$ sebuah string Lyndon.
$^*$ Sebuah string lebih kecil secara leksikografis daripada string lain jika string tersebut merupakan prefiks sejati dari string lainnya, atau jika karakternya pada posisi pertama di mana kedua string berbeda muncul lebih awal dalam alfabet.
$^\dagger$ Sufiks sejati adalah sufiks tak kosong yang tidak sama dengan string aslinya. Sebagai contoh, “qqoj” memiliki $3$ sufiks sejati, yaitu “j”, “oj”, dan “qoj”.
Masukan
Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan jumlah kasus uji.
Untuk setiap kasus uji, baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 3000$). Baris kedua berisi sebuah string $s$ dengan panjang $n$, yang hanya terdiri dari huruf Latin kecil.
Dijamin bahwa jumlah dari $n^2$ di seluruh kasus uji tidak melebihi $9 \times 10^6$.
Keluaran
Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat, yang menyatakan jumlah operasi minimum yang diperlukan untuk menjadikan $s$ sebuah string Lyndon.
Contoh
Masukan 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Keluaran 1
0 1 2 3
Catatan
Pada kasus uji contoh pertama, string tersebut sudah merupakan string Lyndon, sehingga tidak diperlukan operasi apa pun.
Pada kasus uji contoh kedua, Little Cyan Fish dapat mengubah karakter terakhir menjadi b, sehingga memperoleh aaab.
Pada kasus uji contoh ketiga, ia dapat mengubah karakter pertama dan terakhir masing-masing menjadi a dan c, sehingga memperoleh abac. Satu operasi tidaklah cukup.
Pada kasus uji contoh keempat, ia dapat mengubah dua karakter pertama menjadi a dan karakter terakhir menjadi b, sehingga memperoleh aaaab. Tidak mungkin mencapai hal ini dalam kurang dari tiga operasi.