Little Cyan Fish rất thích lý thuyết xâu. Hôm nay, Little Cyan Fish mời bạn tiếp tục nghiên cứu biệt danh của con người cùng cậu ấy.
Trong vũ trụ của Little Cyan Fish, một biệt danh của con người có thể được biểu diễn dưới dạng một xâu chỉ gồm các chữ cái Latinh thường (a đến z). Ví dụ, “qingyu” và “xiuga” là biệt danh của con người, nhưng “Abacde” thì không.
Little Cyan Fish coi một cái tên $s$ là một xâu Lyndon khi và chỉ khi $s$ có thứ tự từ điển nhỏ hơn$^*$ mọi hậu tố thực sự$^\dagger$ $t$ của $s$. Ví dụ, “abacde” là một xâu Lyndon, nhưng “qingyu” không phải là một xâu Lyndon (vì nó không có thứ tự từ điển nhỏ hơn hậu tố thực sự “ingyu” của nó).
Bây giờ, Little Cyan Fish cho bạn một biệt danh con người $s$ có độ dài $n$. Trong một thao tác, bạn có thể chọn một vị trí và thay thế ký tự ở đó bằng bất kỳ chữ cái Latinh thường nào. Hãy tìm số thao tác tối thiểu cần thiết để biến $s$ thành một xâu Lyndon.
$^*$ Một xâu có thứ tự từ điển nhỏ hơn một xâu khác nếu nó là một tiền tố thực sự của xâu kia, hoặc nếu ký tự của nó tại vị trí đầu tiên mà hai xâu khác nhau xuất hiện sớm hơn trong bảng chữ cái.
$^\dagger$ Một hậu tố thực sự là một hậu tố khác rỗng và không bằng xâu ban đầu. Ví dụ, “qqoj” có $3$ hậu tố thực sự, đó là “j”, “oj” và “qoj”.
Dữ liệu vào
Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T \le 10^4$), cho biết số lượng bộ dữ liệu.
Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 3000$). Dòng thứ hai chứa một xâu $s$ có độ dài $n$, chỉ gồm các chữ cái Latinh thường.
Dữ liệu đảm bảo rằng tổng của $n^2$ trên tất cả các bộ dữ liệu không vượt quá $9 \times 10^6$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu, hãy in ra một dòng duy nhất chứa một số nguyên duy nhất, cho biết số thao tác tối thiểu cần thiết để biến $s$ thành một xâu Lyndon.
Ví dụ
Dữ liệu vào 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
Dữ liệu ra 1
0 1 2 3
Ghi chú
Ở bộ dữ liệu ví dụ đầu tiên, xâu đã là một xâu Lyndon nên không cần thao tác nào.
Ở bộ dữ liệu ví dụ thứ hai, Little Cyan Fish có thể đổi ký tự cuối cùng thành b, thu được aaab.
Ở bộ dữ liệu ví dụ thứ ba, cậu ấy có thể đổi ký tự đầu tiên và ký tự cuối cùng lần lượt thành a và c, thu được abac. Một thao tác là không đủ.
Ở bộ dữ liệu ví dụ thứ tư, cậu ấy có thể đổi hai ký tự đầu tiên thành a và ký tự cuối cùng thành b, thu được aaaab. Không thể đạt được điều này với ít hơn ba thao tác.