eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Вы изучаете два древних языка, стремясь доказать, что они тесно связаны. Вы подозреваете, что слова "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ə

Giriş verilənləri #1
1
12 13 2
hakunamatata
hienakulameta
Çıxış verilənləri #1
9
Mənbə 2018 Петрозаводск, Зима, Jagiellonian U, Январь 30, Задача L