Related Languages#9110
You are studying two ancient languages, aiming to prove that they are closely related. You suspect that the words for "push-relabel flow algorithm" in both languages stem from a single ancestor. If so, they contain similar cores, i.e. subwords that do not differ much from each other.
Given two words and , determine the maximum possible , for which there are connected subwords A' in and B' in such that A' and B' have length , and differ on at most positions.
The first line contains the number of test cases z~(1 \le z \le 2000). The descriptions of the test cases follow.
Every test case consists of three lines. The first line contains three numbers n, m, k~(1 \le n, m \le 4000, 0 \le k \le \min(m, n)). In the next two lines there are two strings and , of lengths and , respectively, each consisting of uppercase Latin letters.
The total length of all the words in the input does not exceed 2 \cdot 10^5.
For each test case output a single integer — the maximum possible length of subwords that differ on at most positions.
Example 1