잘 알려지지 않은 사실이지만, 소들에게는 자신들만의 알파벳인 소 알파벳이 있다. 소 알파벳은 a부터 z까지의 알파벳 소문자 \(26\)개로 이루어져 있다. 하지만 소가 소 알파벳을 말할 때에는 우리가 익숙하게 듣는 abcdefghijklmnopqrstuvwxyz와 다른 특정한 순서로 글자들을 나열할 수도 있다.

베시는 시간을 보내기 위해 소 알파벳을 처음부터 끝까지 반복해서 흥얼거리고 있다. 존은 베시가 소 알파벳 전체를 몇 번 흥얼거렸는지 궁금해졌다.

존이 베시에게서 들은 알파벳 소문자 문자열이 주어진다. 존이 이 문자열을 들으려면 베시가 소 알파벳 전체를 최소 몇 번 흥얼거려야 하는지 구하여라. 존은 베시가 흥얼거리는 동안 항상 집중하고 있지는 않았으므로, 베시가 흥얼거린 글자 중 일부를 듣지 못했을 수도 있다. 주어지는 문자열에는 존이 들었다고 기억하는 글자만 들어 있다.

입력

첫째 줄에 a부터 z까지의 알파벳 소문자 \(26\)개가 소 알파벳에서 등장하는 순서대로 주어진다.

둘째 줄에 존이 베시에게서 들은 알파벳 소문자 문자열이 주어진다. 문자열의 길이는 \(1\) 이상 \(1,000\) 이하이다.

출력

베시가 흥얼거려야 하는 소 알파벳 전체의 최소 반복 횟수를 출력한다.

예제 입력 1

abcdefghijklmnopqrstuvwxyz
mood

예제 출력 1

3

예제 설명 1

이 예제에서 소 알파벳의 순서는 일반적인 알파벳의 순서와 같다.

베시는 소 알파벳 전체를 적어도 세 번 흥얼거려야 한다. 다음과 같이 대문자로 표시된 글자만 존이 들었다면, 베시가 소 알파벳 전체를 정확히 세 번 흥얼거리는 것도 가능하다.

abcdefghijklMnOpqrstuvwxyz
abcdefghijklmnOpqrstuvwxyz
abcDefghijklmnopqrstuvwxyz

출처

USACO 2021 January Contest, Bronze, Problem 1. Uddered but not Herd