먼저 가세요

상근이는 친구들과 함께 라인제로 스키장에 왔다. 오전, 오후에는 열심히 스키를 타고, 저녁 때는 근처 바로 가서 술을 마시며 친구들과 놀려고 한다.

라인제로 스키장은 모든 시설이 세계 최고를 자랑하지만, 한 가지 단점이 있다. 바로, 스키 리프트이다. 리프트는 너무 작아서 5초에 한 명씩 태울 수 있다.

보통 친구와 동시에 스키장의 정상에서 내려온다고 해도, 리프트가 있는 곳에는 동시에 도착하지 않는다. 따라서, 리프트를 타기 전에 친구가 내려오기를 기다려야 하고, 리프트에서 내린 이후에도 친구가 내리기를 기다려야 한다.

상근이는 친구가 아직 리프트에 도착하지 않았다면, 줄을 뒤에 있는 사람에게 양보하려고 한다. 상근이의 입장에서 이 상황을 살펴 보면, 상근이가 아낄 수 있는 시간은 없고, 기다리는 장소의 차이만 있을 뿐이다. 하지만, 상근이가 양보한 사람의 관점에서 보면 그 사람이 속한 그룹은 기다리는 시간을 아낄 수 있다. 예를 들어, 그 사람의 친구가 이미 리프트에서 내려서 그 사람을 기다리고 있다고 하면, 그 사람의 친구는 기다리는 시간을 절약하게 된다.

상근이는 모든 사람이 위와 같은 행동을 한다면, 많은 사람들이 기다리는 시간을 절약할 수 있다고 생각한다. 

어떤 사람이 줄을 양보했을 때, 자신이 아끼는 시간은 없지만, 다른 사람이 아끼는 시간이 생긴다면 줄을 양보한다고 가정하자. 더 이상 이 행동을 할 수 없을 때까지 반복했을 때, 총 아낄 수 있는 시간을 얼마나 되는지 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 리프트를 기다리고 있는 사람의 수 n (1 ≤ n ≤ 25,000)이 주어진다. 다음 줄에는 길이가 n인 문자열이 주어진다. 문자열은 알파벳 대문자, 소문자, 숫자로만 이루어져 있다. 문자열은 리프트를 기다리고 있는 사람의 정보를 나타내며, 각 글자는 그 사람이 속한 그룹을 나타낸다. 즉, 같은 글자로 표시된 사람은 같은 친구 그룹에 속하는 사람이다.

각 테스트 케이스마다, 절약한 시간을 출력한다.