Given a string $S$, concatenate it to itself $N$ times, and call the result $S^{\prime }$. 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^{\prime }$. 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 7500$
$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