Вы изучаете два древних языка, стремясь доказать, что они тесно связаны. Вы подозреваете, что слова "push-relabel flow algorithm" в обоих языках происходят от одного предка. Если это так, они содержат одинаковые ядра, то есть подслова, которые не сильно отличаются друг от друга.

Для заданных двух слов $A$ и $B$ определите наибольшее возможное $s$, для которого существуют такие связанные подслова $A'$ в $A$ и $B'$ в $B$ что $A'$ и $B'$ имеют длину $s$, и различаются не более чем в $k$ позициях.

\InputFile Первая строка содержит количество тестов $z~(1 \le z \le 2000)$. Далее следуют описания тестов.

Каждый тест состоит из трех строк. Первая строка содержит три числа $n, m, k~(1 \le n, m \le 4000, 0 \le k \le min(m, n))$. Следующими двумя строками являются $A$ и $B$ с длинами $n$ и $m$ соответственно, и состоят из прописных латинских букв.

Общая длина всех входных слов не превосходит $2 \cdot 10^5$.

\OutputFile Для каждого теста выведите одно целое число --- максимально возможную длину подслов, различающихся не более чем в $k$ позициях.