Momo has a string which he plays with. After each day, he takes the initial string and appends it to the one that he currently has, that is, if the string is "", on the first day the string will remain "", on the second day the string will become "", on the third day the string becomes "", and so on.
Bobo has another string . Bobo is curious whether his string can be found as a subsequence in Momo's string. He is curious what is the first day when this property will hold.
A string is a subsequence of a string if can be obtained from by deletion of several (possibly, zero or all) elements.
The first line of the input contains Momo's string .
The second line of the input contains Bobo's string .
Both strings have lengths at least and at most 5\cdot 10^5 and contain only lowercase letters of the English alphabet.
Output a single integer — the number of the day when Bobo's string will be a subsequence of Momo's string for the first time.
It is guaranteed that for all test cases in this problem such a day exists.
Example 1
During the first day, the string is "dwalkcake", and doesn't contain "cakewalk" as a subsequence.
During the second day, the string is "dwalkcakedwalkcake", and it contains "cakewalk" as a subsequence.