Little known is the fact that cows have their own alphabet "cowphabet". It consists of the same 26 letters from 'a' to 'z', but in a different order.
To pass the time, Besi mumbles cowphabet over and over again. Farmer John wonders how many times she's muttered it.
Given a string of letters that the FD heard from Besie's muttering, determine the minimum number of times Besie must mutter cowphabet for the FD to hear the given string. The FD doesn't always pay attention to Besie's mutterings, so he may not be able to hear some of the Besie's muttering letters. The string given to you contains only those letters that he heard.
Input
The first input line contains 26 small Latin letters from 'a' to 'z' in the order they appear in cowphabet. The next line contains a string of small Latin letters that the FD heard. This string has a length between 1 and 1000.
Imprint
Print the minimum number of times that Bessy muttered the alphabet.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
abcdefghijklmnopqrstuvwxyz
mood
|
3 |
In this example, cowphabet is ordered like a normal alphabet.
Bessie muttered cowphabet at least 3 times. Below is how Besi muttered, and in capital letters what letters FD heard.
abcdefghijklMnOpqrstuvwxyz abcdefghijklmnOpqrstuvwxyz abcDefghijklmnopqrstuvwxyz
|