Нечесний водій

Коли ви прибули в аеропорт імені Шарля де Голля, ви необачно погодилися на пропозицію неофіційного водія підвезти вас до Парижа за "конкурентоспроможними цінами". Це обернулося катастрофою: не лише ціна виявилася надзвичайно високою, але й водій навмисно зробив поїздку набагато довшою, щоб виправдати цю ціну.

Ви зрозуміли, що стали жертвою шахрайства, оскільки вже кілька разів подорожували цим маршрутом. У вас хороша пам'ять, тому ви змогли запам'ятати шлях, яким їхали, включаючи всі зайві петлі, які водій змусив вас пройти.

Зараз ви перебуваєте в поліцейському відділку, щоб подати скаргу на цього водія, і офіцер просить вас розповісти свою історію. Вона навіть просить вас детально описати весь ваш маршрут. Щоб не витрачати на це кілька годин, ви вирішуєте надати стислу версію.

Припустимо, ви пам'ятаєте, що подорожували по місцях $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 }$).

Вихідні дані

Виведіть одне ціле число — розмір найкоротшого стислого шляху.

Приклади

Примітка

Приклад 1. Найкоротша стисла форма шляху: $(((a{)}^{3}b{)}^2(c{)}^{2}d{)}^2$. Містяться в ньому атомарні шляхи: $a,b,c$ і $d$. Отже, розмір шляху дорівнює $4$.

Приклад 2. Найкоротша стисла форма шляху: $(a{)}^{2}ba$. Містяться в ньому атомарні шляхи: $a,b$ і $a$. Отже, розмір шляху дорівнює $3$.