После тяжелого дня Виталий очень проголодался, он хочет съесть свой любимый пирожок с картошкой. Но всё не так просто. Виталий находится в первой комнате дома с n комнатами, расположенными в ряд и пронумерованными с единицы слева направо. Из первой комнаты можно попасть во вторую комнату, из второй комнаты в третью и так далее — из (n - 1)-й комнаты можно попасть в n-ю. Таким образом, в комнату номер x можно попасть только лишь из комнаты номер x - 1.

Пирожок с картошкой находится в n-й комнате, в которую Виталию необходимо попасть.

Между каждой парой последовательных комнат есть дверь. Чтобы попасть в комнату номер x из комнаты номер x - 1 необходимо открыть дверь между комнатами соответствующим ей ключом. Всего в доме существует несколько типов дверей (задаются прописными латинскими буквами) и несколько типов ключей (задаются строчными буквами латинского алфавита). Ключ типа t подходит к двери типа T тогда и только тогда, когда t и T это одна и та же буква, записанная в разных регистрах. Например, ключом f можно открывать двери F.

В каждой из первых n - 1 комнат лежит ровно по одному ключу некоторого типа, которые Виталий может использовать, чтобы попасть в следующие комнаты. После того, как дверь открыта каким-то ключом, Виталий не достаёт ключ из замочной скважины и незамедлительно бежит в следующую комнату. Иными словами, каждым ключом можно открыть не более одной двери.

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

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