Пожалуйста, проходите
В настоящее время Вы катаетесь на лыжах с группой друзей. В общем, все идет хорошо: Вам нравится кататься на лыжах в течение дня и, конечно же, кататься на лыжах в ночное время. Однако есть одна неприятность: лыжный подъемник. Как всегда, он слишком мал и может обслуживать только одного человека каждые 5 секунд. Хуже того, Вы и Ваши друзья обычно не приезжаете одновременно на лифте, а это означает, что Вы проводите время, ожидая в нижней части горы лифта и затем сверху своих друзей.
Ожидание наверху особенно неэффективно. Фактически, Вы понимаете, что если Ваши друзья еще не прибыли, то можете позволить другим людям обойти Вас в очереди. Для Вас это не имеет значения, поскольку в противном случае Вы будете ждать наверху. С другой стороны, Ваши действия могут сэкономить им время, если их друзья уже прибыли и в настоящее время ждут их наверху.
Вам интересно, сколько времени будет выиграно, если все последуют таким хорошим манерам. Вы внимательно наблюдали за очередью и заметили, какие люди образуют группы друзей. Предположим, человек пропустит другого, если это не изменит его собственное время ожидания, но сэкономит время для другого человека. Делайте это снова и снова, пока это возможно. Сколько в общей сложности времени это сохранит?
Входные данные
Первая строка содержит количество тестов, не более 100. Далее для каждого теста:
первая строка содержит число n (1 ≤ n ≤ 25000) - количество людей в ожидании лифта.
вторая строка содержит n символов (большие и малые буквы и числа) - описание очереди. Первый человек в строке представляет человека в голове очереди. Одинаковые символы соответствуют людям из одной группы друзей.
Выходные данные
Для каждого теста выведите в одной строке сохраненное время в секундах.