Задача J. Поход за шляпой

Автор:И. Блинов, А. Кленин   Ограничение времени:10 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

Юная программистка Маша уговорила своего друга Васю сходить с ней в торговый центр и помочь в выборе новой шляпы. Торговый центр состоит из N бутиков, каждый из которых продаёт шляпы определённого бренда. Бренды обозначены малыми латинскими буквами. Один и тот же бренд может встречаться в нескольких бутиках. Бутики расположены в один ряд и пронумерованы от 1 до N.

Маша выбирает шляпу в несколько заходов. Заход номер i состоит из посещения отрезка бутиков с номерами от Li до Ri (1 ≤ Li ≤ Ri ≤ N). Маше нравится процесс выбора, поэтому она хочет сделать как можно больше заходов. Однако, чтобы не слишком сильно испытывать терпение Васи, она решила делать заходы по следующим правилам:

Например, для ряда из 5 бутиков с брендами caabb возможна такая последовательность заходов:

(1, 5), (1, 4), (2, 5), (3, 4), (2, 4), (3, 5), (4, 4), (4, 5), (5, 5).

Требуется написать программу, определяющую по данному набору бутиков максимальное количество заходов, которые могут сделать Маша с Васей.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

За тесты c 1 по 20 начисляется по 2 балла, за остальные (с 21 по 40) по 3 балла.

Формат входного файла

Первая строка входного файла содержит целое число T — количество тестов. Далее идут T описаний тестов, по две строки на описание.

Первая строка каждого теста содержит целое число N — количество бутиков. Вторая строка каждого теста состоит из N малых латинских букв и задаёт последовательность брендов в бутиках.

Формат выходного файла

Выходной файл должен содержать T ответов на тесты.

Каждый ответ состоит из одной строки, содержащей целое число — максимальное количество заходов для соответствующего теста.

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с числом 0.

Ограничения

Буквы брендов находятся в диапазоне от 'a' до 't'.

1 ≤ N ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2
aa
5
caabb
3
9

0.030s 0.006s 17