Родинні мови

Ви вивчаєте дві давні мови, прагнучи довести, що вони тісно пов'язані. Ви підозрюєте, що слова "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$ позиціях.

Приклади