#include <iostream>
#include <set>
#include <vector>
#include <bitset>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <unordered_set>
using namespace std;
vector<string> a;int N,M,K;
vector<bitset<4100>> l1;
vector<bitset<4100>> l2;
vector<bitset<4100>> c(4100);
vector<bitset<4100>> t(4100);
bool comp(int i, int j) {
if(i>j) swap(i,j);
if(c[i][j]) return t[i][j];
bool u = ((l1[i]^l1[j]) | (l2[i]^l2[j])).count() == K;
c[i][j]=true;
t[i][j] = u;
return u;
}
int main()
{
cin>>N>>M>>K;
l1.resize(N);
l2.resize(N);
for (int i = 0; i < N; ++i) {
string s; cin>>s;
a.push_back(s);
for (int j = 0; j < M; ++j) {
l1[i][j]= (s[j]=='A' || s[j]=='C');
l2[i][j]= (s[j]=='A' || s[j]=='G');
}
}
unordered_set<int> s;
vector<int> com;
for (int i = 0; i < N; ++i) {
s.insert(i);
}
while(!s.empty()) {
int u = *s.begin();
for(int v :s) {
if(v==u) continue;
if(!comp(u,v)) {
com.push_back(v);
com.push_back(u);
s.erase(v);
s.erase(u);
goto label1;
}
}
for(int v :com) {
if(v==u) continue;
if(!comp(u,v)) {
com.push_back(u);
s.erase(u);
goto label1;
}
}
cout<<(u+1)<<endl;
exit(0);
label1:
int t =1;
}
}
