Вы изучаете два древних языка, стремясь доказать, что они тесно связаны. Вы подозреваете, что слова "push-relabel flow algorithm" в обоих языках происходят от одного предка. Если это так, они содержат одинаковые ядра, то есть подслова, которые не сильно отличаются друг от друга.
Для заданных двух слов A и B определите наибольшее возможное s, для которого существуют такие связанные подслова A′ в A и B′ в B что A′ и B′ имеют длину s, и различаются не более чем в k позициях.
\InputFileПервая строка содержит количество тестов z (1≤z≤2000). Далее следуют описания тестов.
Каждый тест состоит из трех строк. Первая строка содержит три числа n,m,k (1≤n,m≤4000,0≤k≤min(m,n)). Следующими двумя строками являются A и B с длинами n и m соответственно, и состоят из прописных латинских букв.
Общая длина всех входных слов не превосходит 2⋅105.
\OutputFileДля каждого теста выведите одно целое число --- максимально возможную длину подслов, различающихся не более чем в k позициях.