Given a string ~S~, concatenate it to itself ~N~ times, and call the result ~S'~. Given a string ~T~, you want to find the maximum number ~M~ such that ~T~ concatenated to itself ~M~ times is a subsequence of ~S'~. String ~S~ consists of lowercase English letters and wildcard character &, which can be any lowercase English letter, and string ~T~ consists of only lowercase English letters.

Constraints

~|S|, |T| \le 7\,500~
~N \le 10^{15}~

Input Specification

The first line of input contains string ~S~.
The second line of input contains string ~T~.
The final line has a single integer, ~N~.

Output Specification

Output the value of ~M~.

Sample Input 1

bab
aba
4

Sample Output 1

2

Sample Input 2

ba&
aba
4

Sample Output 2

3