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 A and B, determine the maximum possible s, for which there are connected subwords A′ in A and B′ in B such that A′ and B′ have length s, and differ on at most k positions.
The first line contains the number of test cases z (1≤z≤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≤n,m≤4000,0≤k≤min(m,n)). In the next two lines there are two strings A and B, of lengths n and m, respectively, each consisting of lowercase English letters.
The total length of all the words in the input does not exceed 2⋅105.
For each test case output a single integer — the maximum possible length of subwords that differ on at most k positions.