Родственные языки

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

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

Входные данные

Первая строка содержит количество тестов $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$.

Выходные данные

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

Примеры