19. Наташа-рукодельница

На 8 марта Наташа решила подарить маме бусы, сделанные своими руками. Для этого девочка купила специальный набор для рукоделия. В него входили бусины разного размера, цвета и форм. Каждый вид бусин обозначен определенной буквой латинского алфавита. А к набору прилагается схема, которая представляет из себя последовательность латинских букв.

Младший брат Наташи взял бусы и начал выписывать цвет бусин один за одним. При этом он мог прокрутить бусы несколько раз, причём последний оборот не обязательно целиком.

Бусы потерялись и оригинальная схема тоже. И Наташа решила воспользоваться записями брата, чтобы сделать еще одни. К сожалению, не все записи брата можно разобрать, но можно попробовать сделать хоть какие-то бусы, которые бы удовлетворяли всем разборчивым символам.

Определите наименьшее возможное количество бусин в бусах.

В первой строке задано одно целое число $n$ ($1 \le n \le 1000$) – количество символов в записях брата.

Вторая строка содержит последовательность бусин в записях. Она состоит из $n$ символов – строчных букв латинского алфавита и знака #, который обозначает, что букву на этой позиции невозможно распознать.

Выведите одно целое положительное число – наименьшее возможное количество бусин в подходящей схеме.

В первом примере все буквы удалось распознать, минимальная смеха может состоять из 3 бусин – abc.

Во втором примере все буквы удалось распознать, минимальная схема может состоять из 3 бусин – abb. Обратите внимание, что вторая и третья бусинки в этой схеме одинаковые.

В третьем примере наименьшая возможная длина схемы получается, если предположить, что на третьей позиции находился бусинка a. Тогда исходная строка – ababa, минимальная схема состоит из 2 бусинок – ab.

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