#include<bits/stdc++.h>
#define sz(v) (int)(v.size())
using namespace std;
const int sz = 16810005;
int t[sz][5];
vector<pair<int, int>>vect;
vector<int> idc[sz];
int mm[sz];
void f(int st, int ed, int k)
{
if(k < 0)
return;
if(t[st][0] == -1 && t[st][1] == -1 && t[st][2] == -1 && t[st][3] == -1)
{
if(!k)
{
mm[st] += sz(idc[ed]);
mm[ed] += sz(idc[st]);
}
return;
}
if(st == ed)
{
for(int i = 0; i < 4; i++)
{
if(t[st][i] == -1)
continue;
for(int j = i; j < 4; j++)
{
if(t[ed][j] == -1)
continue;
int cst = 1 - (i == j);
f(t[st][i], t[ed][j], k-cst);
}
}
return;
}
for(int i = 0; i < 4; i++)
{
if(t[st][i] == -1)
continue;
for(int j = 0; j < 4; j++)
{
if(t[ed][j] == -1)
continue;
int cst = 1 - (i == j);
f(t[st][i], t[ed][j], k-cst);
}
}
}
void solve()
{
int n, m, k, i, j;
cin >> n >> m >> k;
string s[n+5];
for(i = 1; i <= n; i++)
{
cin >> s[i];
s[i] = "#" + s[i];
}
map<char, int>mp;
mp['A'] = 0;
mp['C'] = 1;
mp['G'] = 2;
mp['T'] = 3;
int nd = 1, idx = 1;
for(i = 1; i <= n * m + 2; i++)
t[i][0] = t[i][1] = t[i][2] = t[i][3] = -1;
for(i = 1; i <= n; i++)
{
nd = 1;
for(j = 1; j <= m; j++)
{
if(t[nd][mp[s[i][j]]] == -1)
{
idx++;
t[nd][mp[s[i][j]]] = idx;
nd = idx;
}
else
nd = t[nd][mp[s[i][j]]];
if(j == m)
idc[nd].push_back(i);
}
}
f(1, 1, k);
for(i = 1; i <= idx; i++)
{
if(mm[i] == n - 1)
{
cout << idc[i][0] << "\n";
return;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tests = 1;
//cin >> tests;
while(tests--)
{
solve();
}
}
