Мендо мноогу сака да јаде чоколадо, па не сака да работи и да ги оценува решенијата на задачите се додека не му го купиме омиленото чоколадо. Мендо особено ги сака чоколадите ZIM&ZIM, бидејќи тие се составени од еден ред на коцкички, каде во секоја коцка има по точно една голема буква од латиничната азбука 'A'-'Z'.

Мендо сака да ги јаде само коцките од чоколадите на кои е запишана одредена буква. Притоа, го интересира колку најмалку пати треба да го скрши чоколадото за да ги оддели сите коцки во кои е запишана бараната буква од останатите коцки.

Напишете програма која за даден изглед на чоколадото и барана буква, ќе го пресмета најмалиот број на прекршувања на чоколадото, така што од него се одделат сите делови со бараната буква.

Влез

Во првата линија е запишан изгледот на чоколадото – како низа од знаци, составена само од големите латинични букви 'A'-'Z'. Должината на низата е најмногу 200. Секој знак од низата означува која буква е запишана на соодветната коцка од чоколадото.

Во втората линија е запишана бараната буква ('A'-'Z'), која секогаш ќе се појави барем еднаш во низата која го дефинира изгледот на чоколадото.

Излез

Излезот се состои од еден цел број – најмалиот број на кршења на чоколадото.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
BIIKIIIOKIIJK
I

излез
6

влез
ZZKZZZZZZ
Z

излез
2

Објаснување за првиот пример: Чоколадото треба да го скршиме 6 пати. Притоа, деловите ќе бидат 'B', 'II', 'K', 'III', 'OK', 'II', 'JK'. Забележете дека со тоа се одвоени сите коцки со буквата 'I'.