Given a string , concatenate it to itself times, and call the result . Given a string , you want to find the maximum number such that concatenated to itself times is a subsequence of . String consists of lowercase English letters and wildcard character &
, which can be any lowercase English letter, and string consists of only lowercase English letters.
Constraints
Input Specification
The first line of input contains string .
The second line of input contains string .
The final line has a single integer, .
Output Specification
Output the value of .
Sample Input 1
bab
aba
4
Sample Output 1
2
Sample Input 2
ba&
aba
4
Sample Output 2
3
Comments