먼저 가세요

상근이는 친구들과 함께 스키장에 왔다. 낮에는 스키를 타고, 저녁에는 근처 술집에 모여 함께 시간을 보낸다.

이 스키장의 리프트는 매우 작아서 5초에 한 명씩만 태울 수 있다. 그래서 사람들은 리프트를 타기 위해 한 줄로 서서 차례를 기다린다.

한 그룹의 친구들은 함께 다니려고 하지만, 정상에서 동시에 출발해도 리프트 앞에는 서로 다른 시각에 도착한다. 그래서 리프트를 타기 전에는 먼저 도착한 사람이 뒤에 오는 친구를 기다려야 하고, 리프트에서 내린 뒤에도 아직 도착하지 않은 친구를 기다려야 한다. 결국 한 그룹은 그 그룹의 마지막 사람이 리프트를 타야 비로소 모두 모여 함께 이동할 수 있다.

어떤 사람은 자기 그룹의 친구가 아직 리프트 줄에 도착하지 않았다면, 바로 뒤에 서 있는 사람에게 순서를 양보할 수 있다. 이렇게 양보하더라도 양보한 사람 본인이 아끼는 시간은 없다. 단지 기다리는 위치만 바뀔 뿐이다. 하지만 앞으로 나온 사람이 속한 그룹은, 이미 리프트를 타고 올라가 기다리고 있던 친구를 더 빨리 다시 만나게 되어 기다리는 시간을 줄일 수 있다.

모든 사람이 "자신은 손해가 없지만 다른 그룹이 시간을 아낄 수 있을 때에는 순서를 양보한다"는 규칙을 따른다고 하자. 더 이상 양보가 일어날 수 없을 때까지 이 과정을 반복했을 때, 모든 그룹이 아낄 수 있는 시간의 총합(초)을 구하여라.

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

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

각 테스트 케이스마다, 모든 그룹이 아낄 수 있는 시간의 총합을 초 단위로 한 줄에 하나씩 출력한다.