Нечестный водитель

Когда Вы прибыли в аэропорт имени Шарля де Голля, то наивно согласились подвезти до Парижа неуполномоченного водителя, который предложил Вам "конкурентоспособные цены". Конечным результатом стала катастрофа: мало того, что цена была чрезвычайно высокой, так еще и водитель сделал поездку намного дольше, чем необходимо, чтобы оправдать эту цену.

Вы заметили аферу, потому что уже несколько раз путешествовали по одному и тому же месту. У Вас хорошая память, поэтому Вы в состоянии хорошо запомнить путь, которым следовали, включая каждую из петель, которые мошенник заставил вас пройти.

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

Предположим, Вы помните, что путешествовали по местам $A,B,C,D,A,B,C,D$. В этом случае лучше сказать офицеру: "Я дважды прошел по пути $ABCD$", а не "Я прошел по пути $ABCDABCD$". Учитывая, что Ваш путь повторял одну и ту же последовательность мест, это значительно сократит изложение, не упустив при этом ни одной детали.

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

• одно место, через которое Вы путешествовали, называемое "атомарным путем";

• объединение двух сжатых путей;

• повторение сжатого пути, т. е. $(C{)}^n$. Это означает, что Вы прошли путь $Cn$ раз подряд.

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

Входные данные

Состоит из двух строк:

• Первая строка содержит одно целое число $n(0<n\le 700)$ — длину пути.

• Вторая строка содержит путь в виде строки размера $n$. Каждое местоположение описывается буквенно-цифровым символом: цифрой (от ${}^{\prime }{0}^{\prime }$ до ${}^{\prime }{9}^{\prime }$), строчной буквой (от ${}^{\prime }{a}^{\prime }$ до ${}^{\prime }{z}^{\prime }$) или прописной буквой (от ${}^{\prime }{a}^{\prime }$ до ${}^{\prime }{z}^{\prime }$). от ${}^{\prime }{A}^{\prime }$ до ${}^{\prime }{Z}^{\prime }$).

Выходные данные

Выведите одно целое число — размер кратчайшего сжатого пути.

Примеры

Примечание

Пример 1. Кратчайшая сжатая форма пути: $(((a{)}^{3}b{)}^2(c{)}^{2}d{)}^2$. Содержащиеся в нем атомарные пути: $a,b,c$ и $d$. Следовательно, размер пути равен $4$.

Пример 2. Кратчайшая сжатая форма пути: $(a{)}^{2}ba$. Содержащиеся в нем атомарные пути: $a,b$ и $a$. Следовательно, размер пути равен $3$.