Родственные языки
Родственные языки
Вы изучаете два древних языка, стремясь доказать, что они тесно связаны. Вы подозреваете, что слова "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 позициях.
Nümunə
1 12 13 2 hakunamatata hienakulameta
9