I. The last String bender
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad, the legendary (and slightly unhinged) String Bender, has decided to torture his innocent strings once again!

You are given two non-empty strings $$$s$$$ and $$$t$$$, both consisting of lowercase English letters, and an integer $$$k$$$.

In a single operation, you may insert any lowercase English letter at any position in $$$s$$$—before its first character, after its last character, or between any two adjacent characters. You must perform exactly $$$k$$$ operations, resulting in a string of length $$$|s| + k$$$.

An occurrence of $$$t$$$ is defined as a contiguous substring equal to $$$t$$$. Overlapping occurrences are allowed and counted independently.

Find the maximum possible number of occurrences of $$$t$$$ in the modified string after performing exactly $$$k$$$ insertions.

Input

The first line contains the string $$$s$$$ ($$$1 \le |s| \le 10$$$).

The second line contains the string $$$t$$$ ($$$1 \le |t| \le 10$$$).

The third line contains an integer $$$k$$$ ($$$0 \le k \le 10^7$$$).

Both strings consist only of lowercase English letters.

Output

Print one integer — the maximum possible number of occurrences of $$$t$$$ after inserting exactly $$$k$$$ characters into $$$s$$$.

Examples
Input
aa
aa
2
Output
3
Input
b
ab
3
Output
2
Input
abc
bc
0
Output
1
Input
spongebob
stringbend
1000
Output
100
Note

In the first example, insert two letters to obtain aaaa. The string aa occurs starting at positions $$$1$$$, $$$2$$$, and $$$3$$$. These occurrences overlap.

In the second example, it is possible to obtain abab. The string ab then occurs twice.