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