#include #include #include #include #include #include #define foreach(T,p,c) for(T p = (c).begin(); p != (c).end(); p++) using namespace std; struct person_t { int h; // [h]eight char g; // [g]ender string m; // [m]usic string s; // [s]port }; bool couple(const person_t &p1, const person_t &p2) { if(abs(p1.h - p2.h) > 40) return false; if(p1.g == p2.g) return false; if(p1.m != p2.m) return false; if(p1.s == p2.s) return false; return true; } void core(ifstream &fin) { int n; fin >> n; vector< vector > adj; int nx, ny; { vector px; vector py; for(int i = 0; i < n; i++) { person_t p; fin >> p.h >> p.g >> p.m >> p.s; if(p.g == 'M') px.push_back(p); else py.push_back(p); } nx = px.size(); ny = py.size(); adj.assign(nx, vector(ny)); for(int x = 0; x < nx; x++) { for(int y = 0; y < ny; y++) { adj[x][y] = couple(px[x], py[y]); } } } vector y2x(ny, -1); { for(int s = 0; s < nx; s++) { vector px(nx, -1); queue qx; vector py(ny, -1); queue qy; px[s] = ny; qx.push(s); int t = ny; while(!qx.empty()) { // x -> y while(!qx.empty()) { int x = qx.front(); qx.pop(); for(int y = 0; y < ny; y++) { if(adj[x][y] && py[y] < 0 && y2x[y] != x) { py[y] = x; qy.push(y); if(y2x[y] < 0) { t = y; goto found; } } } } // y -> x while(!qy.empty()) { int y = qy.front(); qy.pop(); int x = y2x[y]; if(px[x] < 0) { px[x] = y; qx.push(x); } } } found: for(int y = t; y < ny; y = px[py[y]]) y2x[y] = py[y]; } } int m = count(y2x.begin(), y2x.end(), -1); cout << nx + m << endl; } int main(void) { ifstream fin("guardian.in"); int n; fin >> n; for(int i = 0; i < n; i++) core(fin); return 0; }