Qohum dillər#9110
Siz iki qədim dili öyrənirsiniz və onların bir-biri ilə sıx bağlı olduğunu sübut etməyə çalışırsınız. Siz "push-relabel flow algorithm" sözlərinin hər iki dildə eyni kökdən gəldiyini düşünürsünüz. Əgər belədirsə, onlar eyni nüvələrə malikdirlər, yəni bir-birindən çox fərqlənməyən alt sözlərə malikdirlər.
Verilmiş iki söz və üçün, -da A' və -də B' əlaqəli alt sözlərin mövcud olduğu ən böyük mümkün -i müəyyən edin ki, A' və B' uzunluğu -dir və mövqedən çox fərqlənmirlər.
Birinci sətir testlərin sayı z~(1 \le z \le 2000)-ni ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər bir test üç sətirdən ibarətdir. Birinci sətir üç ədəd n, m, k~(1 \le n, m \le 4000, 0 \le k \le \min(m, n)) ehtiva edir. Növbəti iki sətir və uzunluqlu və BÖYÜK LATIN HƏRFLƏRİNDƏN ibarət olan və -dir.
Bütün giriş sözlərinin ümumi uzunluğu 2 \cdot 10^5-dən çox deyil.
Hər bir test üçün mövqedən çox fərqlənməyən alt sözlərin mümkün olan maksimal uzunluğunu göstərən bir tam ədəd çıxarın.
Nümunə 1