#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n,i,j,m,g[1100][1100],a[1100],l[1100],list[1100],head,tail,ans; char s[1100][1100]; bool v[1100],u[1100]; char temp[2100]; bool matching(int x,int y) { int l,r; memcpy(temp,s[x],sizeof(char)*strlen(s[x])+sizeof(char)); strcat(temp,s[y]); l=0; r=strlen(temp)-1; while (l<r && temp[l]==temp[r]) { l++; r--; } if (l>=r) return 1; memcpy(temp,s[y],sizeof(char)*strlen(s[y])+sizeof(char)); strcat(temp,s[x]); l=0; r=strlen(temp)-1; while (l<r && temp[l]==temp[r]) { l++; r--; } if (l>=r) return 1; return 0; } bool dfs(int d) { if (v[d]) return 0; v[d]=1; int k; for (k=1;k<=a[d];k++) if (!l[g[d][k]] || dfs(l[g[d][k]])) { l[g[d][k]]=d; return 1; } return 0; } int main() { while (scanf("%d",&n)==1) { for (i=1;i<=n;i++) scanf("%s",s[i]); memset(a,0,sizeof(a)); for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) if (matching(i,j)) { a[i]++; g[i][a[i]]=j; a[j]++; g[j][a[j]]=i; } ans=0; memset(u,0,sizeof(u)); memset(l,0,sizeof(l)); for (i=1;i<=n;i++) if (!u[i]) { u[i]=1; head=0; tail=1; list[head]=i; while (head<tail) { for (j=1;j<=a[list[head]];j++) if (!u[g[list[head]][j]]) { u[list[tail]=g[list[head]][j]]=1; tail++; } head++; } m=0; for (j=0;j<tail;j++) { memset(v,0,sizeof(v)); if (dfs(list[j])) m++; } ans+=tail-m/2; } printf("%d\n",ans); } return 0; }