Родинні мови#9110
Ви вивчаєте дві давні мови, прагнучи довести, що вони тісно пов'язані. Ви підозрюєте, що слова "push-relabel flow algorithm" в обох мовах походять від одного предка. Якщо це так, вони містять однакові ядра, тобто підслова, які не сильно відрізняються одне від одного.
Для заданих двох слів і визначте найбільше можливе , для якого існують такі пов'язані підслова A' в і B' в , що A' і B' мають довжину , і відрізняються не більше ніж у позиціях.
Перша стрічка містить кількість тестів z~(1 \le z \le 2000). Далі йдуть описи тестів.
Кожен тест складається з трьох стрічок. Перша стрічка містить три числа n, m, k~(1 \le n, m \le 4000, 0 \le k \le \min(m, n)). Наступними двома стрічками є і з довжинами і відповідно, і складаються з ВЕЛИКИХ ЛАТИНСЬКИХ ЛІТЕР.
Загальна довжина всіх вхідних слів не перевищує 2 \cdot 10^5.
Для кожного тесту виведіть одне ціле число — максимально можливу довжину підслів, що відрізняються не більше ніж у позиціях.
Приклад 1