#include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <cstring> #include <cctype> #include <string> #include <vector> #include <list> #include <set> #include <map> #include <queue> #include <stack> #include <algorithm> #include <functional> using namespace std; #define DEBUG(x) cout << '>' << #x << ':' << x << endl; #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define FORD(i,a,b) for(int i=(a);i>=(b);i--) inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; } const int INF = 1<<29; typedef long long ll; inline int two(int n) { return 1 << n; } inline int test(int n, int b) { return (n>>b)&1; } inline void set_bit(int & n, int b) { n |= two(b); } inline void unset_bit(int & n, int b) { n &= ~two(b); } inline int last_bit(int n) { return n & (-n); } inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; } template<class T> void chmax(T & a, const T & b) { a = max(a, b); } template<class T> void chmin(T & a, const T & b) { a = min(a, b); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////// const int MAX = 1007; const int MUL = 31; int N; char in[MAX][MAX]; int len[MAX]; ll hs[MAX][2]; ll pw[MAX]; vector<int> graph[MAX]; int match[MAX], p[MAX], base[MAX]; bool used[MAX], blossom[MAX], used2[MAX]; int lca(int a, int b) { REP(i, N) used2[i] = false; while (true) { a = base[a]; used2[a] = true; if (match[a] == -1) break; a = p[match[a]]; } while (true) { b = base[b]; if (used2[b]) return b; b = p[match[b]]; } } void markPath(int v, int b, int children) { for (; base[v] != b; v = p[match[v]]) { blossom[base[v]] = blossom[base[match[v]]] = true; p[v] = children; children = match[v]; } } int find_path(int root) { REP(i, N) used[i] = false; REP(i, N) p[i] = -1; REP(i, N) base[i] = i; used[root] = true; queue<int> manage; manage.push(root); while (!manage.empty()) { int v = manage.front(); manage.pop(); REP(i, graph[v].size()) { int to = graph[v][i]; if (base[v] == base[to] || match[v] == to) continue; if (to == root || match[to] != -1 && p[match[to]] != -1) { REP(i, N) blossom[i] = false; int curbase = lca(v, to); markPath(v, curbase, to); markPath(to, curbase, v); REP(i, N) if (blossom[base[i]]) { base[i] = curbase; if (!used[i]) { used[i] = true; manage.push(i); } } } else if (p[to] == -1) { p[to] = v; if (match[to] == -1) return to; to = match[to]; used[to] = true; manage.push(to); } } } return -1; } int main() { pw[0] = 1; FOR(i, 1, MAX-1) pw[i] = pw[i-1] * MUL; while (scanf("%d", &N) == 1) { REP(i, N) { graph[i].clear(); scanf("%s", in+i); len[i] = strlen(in[i]); hs[i][0] = hs[i][1] = 0; REP(j, len[i]) { hs[i][0] += pw[j+1] * (in[i][j]-'a'+1); hs[i][1] += pw[j+1] * (in[i][len[i]-1-j]-'a'+1); } } REP(i, N) REP(j, i) { ll h0 = (hs[i][0] + hs[j][0] * pw[len[i]]), h1 = (hs[i][1] * pw[len[j]] + hs[j][1]); ll h2 = (hs[j][0] + hs[i][0] * pw[len[j]]), h3 = (hs[j][1] * pw[len[i]] + hs[i][1]); if (h0 == h1 || h2 == h3) { graph[i].push_back(j); graph[j].push_back(i); } } int result = N; REP(i, N) { match[i] = -1; p[i] = 0; } REP(i, N) { if (match[i] == -1) { int v = find_path(i); if (v != -1) --result; while (v != -1) { int pv = p[v]; int ppv = match[pv]; match[v] = pv; match[pv] = v; v = ppv; } } } printf("%d\n", result); } return 0; }