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.
The first line of input contains string .
The second line of input contains string . The final line has a single integer, .
Output the value of .
Sample Input 1
bab aba 4
Sample Output 1
Sample Input 2
ba& aba 4
Sample Output 2