Qohum dillər

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 $A$ və $B$ üçün, $A$-da $A^{\prime }$ və $B$-də $B^{\prime }$ əlaqəli alt sözlərin mövcud olduğu ən böyük mümkün $s$-i müəyyən edin ki, $A^{\prime }$ və $B^{\prime }$ uzunluğu $s$-dir və $k$ mövqedən çox fərqlənmirlər.

Giriş verilənləri

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 $n$ və $m$ uzunluqlu və böyük latın hərflərindən ibarət olan $A$ və $B$-dir.

Bütün giriş sözlərinin ümumi uzunluğu $2\cdot 10^5$-dən çox deyil.

Çıxış verilənləri

Hər bir test üçün $k$ 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ələr