After a hard day Vitaly got very hungry and he wants to eat his favorite potato pie. But it’s not that simple. Vitaly is in the first room of the house withnroom located in a line and numbered starting from one from left to right. You can go from the first room to the second room, from the second room to the third room and so on — you can go from the (n-1)-th room to then-th room. Thus, you can go to roomxonly from roomx-1.
The potato pie is located in then-th room and Vitaly needs to go there.
Each pair of consecutive rooms has a door between them. In order to go to roomxfrom roomx-1, you need to open the door between the rooms with the corresponding key.
In total the house has several types of doors (represented by uppercase Latin letters) and several types of keys (represented by lowercase Latin letters). The key of typetcan open the door of typeTif and only iftandTare the same letter, written in different cases. For example, keyfcan open doorF.
Each of the firstn-1rooms contains exactly one key of some type that Vitaly can use to get to next rooms. Once the door is open with some key, Vitaly won’t get the key from the keyhole but he will immediately run into the next room. In other words, each key can open no more than one door.
Vitaly realizes that he may end up in some room without the key that opens the door to the next room. Before the start his run for the potato pie Vitaly can buy any number of keys of any type that is guaranteed to get to roomn.
Given the plan of the house, Vitaly wants to know what is the minimum number of keys he needs to buy to surely get to the roomn, which has a delicious potato pie. Write a program that will help Vitaly find out this number.
，别人失去了信心，他却下决心实现自己的目标。
