#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pb push_back
#define sz(v) (ll)(v.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
const ll sz = 16810005;
ll t[sz][5];
vector<pll>vect;
vl idc[sz];
void f(ll st, ll ed, ll k)
{
if(k < 0)
return;
if(t[st][0] == -1 && t[st][1] == -1 && t[st][2] == -1 && t[st][3] == -1)
{
if(!k)
{
for(auto u : idc[st])
{
for(auto h : idc[ed])
vect.pb({u, h});
}
}
return;
}
if(st == ed)
{
for(ll i = 0; i < 4; i++)
{
if(t[st][i] == -1)
continue;
for(ll j = i; j < 4; j++)
{
if(t[ed][j] == -1)
continue;
ll cst = 1 - (i == j);
f(t[st][i], t[ed][j], k-cst);
}
}
return;
}
for(ll i = 0; i < 4; i++)
{
if(t[st][i] == -1)
continue;
for(ll j = 0; j < 4; j++)
{
if(t[ed][j] == -1)
continue;
ll cst = 1 - (i == j);
f(t[st][i], t[ed][j], k-cst);
}
}
}
void solve()
{
ll 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, ll>mp;
mp['A'] = 0;
mp['C'] = 1;
mp['G'] = 2;
mp['T'] = 3;
ll 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].pb(i);
}
}
f(1, 1, k);
map<ll, ll>mm;
for(auto u : vect)
{
mm[u.f]++;
mm[u.s]++;
}
for(i = 1; i <= n; i++)
{
if(mm[i] == n - 1)
{
cout << i << "\n";
return;
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll tests = 1;
//cin >> tests;
while(tests--)
{
solve();
}
}
