Little Cyan Fish는 문자열 이론을 매우 좋아합니다. 오늘 Little Cyan Fish는 당신에게 함께 인간의 닉네임을 계속 연구하자고 초대합니다.
Little Cyan Fish의 우주에서 인간의 닉네임은 영어 소문자(a부터 z까지)로만 이루어진 문자열로 나타낼 수 있습니다. 예를 들어, “qingyu”와 “xiuga”는 인간의 닉네임이지만, “Abacde”는 그렇지 않습니다.
Little Cyan Fish는 이름 $s$가 $s$의 모든 진접미사$^\dagger$ $t$보다 사전순으로 작을$^*$ 때, 그리고 그때에만 $s$를 린든 문자열(Lyndon string)이라고 여깁니다. 예를 들어, “abacde”는 린든 문자열이지만, “qingyu”는 린든 문자열이 아닙니다(그 진접미사 “ingyu”보다 사전순으로 작지 않기 때문입니다).
이제 Little Cyan Fish가 길이 $n$인 인간의 닉네임 $s$를 당신에게 줍니다. 한 번의 연산으로 당신은 하나의 위치를 골라 그 위치의 문자를 임의의 영어 소문자로 바꿀 수 있습니다. $s$를 린든 문자열로 만들기 위해 필요한 최소 연산 횟수를 구하세요.
$^*$ 어떤 문자열이 다른 문자열의 진접두사이거나, 두 문자열이 처음으로 달라지는 위치의 문자가 알파벳 순서상 더 앞에 오면 그 문자열은 다른 문자열보다 사전순으로 작습니다.
$^\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$를 린든 문자열로 만들기 위해 필요한 최소 연산 횟수를 나타내는 정수 하나를 한 줄에 출력합니다.
예제
입력 1
4 4 abac 4 aaaa 4 bbaa 5 bbaaa
출력 1
0 1 2 3
참고
첫 번째 예제 테스트 케이스에서 문자열은 이미 린든 문자열이므로 연산이 필요하지 않습니다.
두 번째 예제 테스트 케이스에서 Little Cyan Fish는 마지막 문자를 b로 바꾸어 aaab를 얻을 수 있습니다.
세 번째 예제 테스트 케이스에서 그는 첫 번째 문자와 마지막 문자를 각각 a와 c로 바꾸어 abac를 얻을 수 있습니다. 한 번의 연산으로는 충분하지 않습니다.
네 번째 예제 테스트 케이스에서 그는 처음 두 문자를 a로 바꾸고 마지막 문자를 b로 바꾸어 aaaab를 얻을 수 있습니다. 세 번 미만의 연산으로 이를 달성하는 것은 불가능합니다.