AB-words

An ab-word is any sequence of the lowercase letters a and b, including the empty sequence. If $X = [x_1, \dots, x_n]$ is an ab-word and $1 \le i \le j \le n$, then $X[i..j]$ denotes the subword $x_i, \dots, x_j$.

An ab-word $X = [x_1, \dots, x_n]$ is nice if it has exactly as many a's as b's, and for every $i = 1, \dots, n$ the prefix $X[1..i]$ has at least as many a's as b's.

The similarity of nice ab-words is defined inductively:

• Any two empty ab-words are similar.
• Two non-empty nice ab-words $X = [x_1, \dots, x_n]$ and $Y = [y_1, \dots, y_m]$ are similar if they have the same length ($n = m$) and at least one of the following holds:
  • $x_1 = y_1$, $x_n = y_n$, and $X[2..n-1]$ and $Y[2..n-1]$ are both nice and similar to each other; or
  • there exists an index $i$ with $1 \le i \le n$ such that $X[1..i]$ and $X[i+1..n]$ are both nice, and one of:
    • $Y[1..i]$ and $Y[i+1..n]$ are both nice, $X[1..i]$ is similar to $Y[1..i]$, and $X[i+1..n]$ is similar to $Y[i+1..n]$; or
    • $Y[1..n-i]$ and $Y[n-i+1..n]$ are both nice, $X[1..i]$ is similar to $Y[n-i+1..n]$, and $X[i+1..n]$ is similar to $Y[1..n-i]$.

The level of diversity of a non-empty set $S$ of nice ab-words is the largest number of words that can be chosen from $S$ so that no two chosen words are similar to each other.

Write a program that reads the set $S$ from standard input, computes the level of diversity of $S$, and writes the result to standard output.

The first line contains an integer $n$, the number of elements of the set $S$ ($1 \le n \le 1000$). Each of the next $n$ lines contains one element of $S$, that is, a nice ab-word. Every word starts at the beginning of its line and has no spaces between consecutive letters. The length of each ab-word is between $1$ and $200$.

Output a single integer: the level of diversity of $S$.