3053: Delete String

As a acmer, $Slp$ is always thinking of problems, and a new problem come to his mind. Given two stings $A$ and $B$, one can delete some characters of $A$ to get a new string $A'$ to make $A'$ and $B$ become a great match.

A great match of $A'$ and $B$ is defined as follow:

1. $S'$ has length of $k$, $B$ has length of $m$ $(k \leq m)$.
2. Define a substring of $B(B_{1}, B_{2}, B{k}])$, as a new string $B'$ with the same length as $A'$. For example, if $A'$ has length of $3$ and $B$ is $``abcde"$, the $B'$ will be $``abc"$.
3. There are exactly $p$($p$ is a given number) $i$ that satisfy $B'_{i} \neq A'_{i}$.

If $A'$ and $B$ meet all the above conditions, we call $A'$ and $B$ is a great match.

Given two string $A$, $B$ and a number $p$, your should help $Slp$ to find the minimum number of deleting characters to get a string $A'$ that has a great match with $B$.

For example, if $A$ is $``aabbcc"$, $B$ is $``abcbc"$ and $p$ is 1, $Slp$ can delete the $2^{nd}$, the $4^{th}$ characters to get $``abcc"$ as $B'$. Then $B'$ is $``abcb"$.So $A'$ and $B'$ has exactly $1$ different location. So the answer is $2$.

Note that $Slp$ may delete all characters of $A$.

The first line contains an integer number $T$, the number of test cases.

For each test case :
The first line contains three integers $n, m, p(0 \leq n, m, p \leq 10^{3})$, length of $S$, $T$ and the number $p$.

The second line contains a string $A$ with the length of $n$.

The third line contains a string $B$ with the length of $m$.

It is guaranteed that the strings contains only lowercase letters.

For each test case print the minimum number of deleting characters to get a string $S'$ that has a great match with $T$. If there is no such way print $-1$.

3
6 5 1
aabbcc
abcbc
4 4 3
aacc
aaba
2 5 0
ac
bbdcc

2
-1
2