eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пожалуйста, проходите

Пожалуйста, проходите

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

В настоящее время Вы катаетесь на лыжах с группой друзей. В общем, все идет хорошо: Вам нравится кататься на лыжах в течение дня и, конечно же, кататься на лыжах в ночное время. Однако есть одна неприятность: лыжный подъемник. Как всегда, он слишком мал и может обслуживать только одного человека каждые 5 секунд. Хуже того, Вы и Ваши друзья обычно не приезжаете одновременно на лифте, а это означает, что Вы проводите время, ожидая в нижней части горы лифта и затем сверху своих друзей.

Ожидание наверху особенно неэффективно. Фактически, Вы понимаете, что если Ваши друзья еще не прибыли, то можете позволить другим людям обойти Вас в очереди. Для Вас это не имеет значения, поскольку в противном случае Вы будете ждать наверху. С другой стороны, Ваши действия могут сэкономить им время, если их друзья уже прибыли и в настоящее время ждут их наверху.

Вам интересно, сколько времени будет выиграно, если все последуют таким хорошим манерам. Вы внимательно наблюдали за очередью и заметили, какие люди образуют группы друзей. Предположим, человек пропустит другого, если это не изменит его собственное время ожидания, но сэкономит время для другого человека. Делайте это снова и снова, пока это возможно. Сколько в общей сложности времени это сохранит?

Вхідні дані

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • первая строка содержит число n (1n25000) - количество людей в ожидании лифта.

  • вторая строка содержит n символов (большие и малые буквы и числа) - описание очереди. Первый человек в строке представляет человека в голове очереди. Одинаковые символы соответствуют людям из одной группы друзей.

Вихідні дані

Для каждого теста выведите в одной строке сохраненное время в секундах.

Приклад

Вхідні дані #1
2
6
AABABB
10
Ab9AAb2bC2
Вихідні дані #1
15
45
Джерело 2011 ACM Northwestern Europe (NWERC), Задача E