Description

每一个由字母 a 和 b 组成的序列（或是空序列），称为 ab-word。

如果 X = [x1, …, xn] 是一个 ab-word，并且有整数 i, j（1 <= i <= j <= n），那么 X[i..j] 表示由字母 xi, …, xj 组成的 X 的子串。

如果一个 ab-word X = [x1, …, xn] 满足：

• 字母 a 的个数等于字母 b 的个数；
• 对任意 i = 1, …, n，在前缀 X[1..i] 中，字母 a 的个数不少于字母 b 的个数；

则称该 ab-word X 为 好的（good）。

下面给出两个好的 ab-words 之间“相似”的递归定义：

• 任意两个空 ab-word（字符串内无字母）是相似的。

• 两个非空的好 ab-words X = [x1, …, xn] 和 Y = [y1, …, ym] 是相似的，当且仅当 n = m 且满足以下条件之一：

  1. x1 = y1，xn = yn，并且 X[2..n-1] 与 Y[2..n-1] 相似，且它们都是好的 ab-words。

  2. 存在 i（1 <= i <= n），使得 X[1..i] 和 X[i+1..n] 都是好的 ab-words，并且满足下列之一：

     a. Y[1..i]、Y[i+1..n] 也是好的 ab-words，且
     X[1..i] 与 Y[1..i] 相似，X[i+1..n] 与 Y[i+1..n] 相似；

     b. Y[1..n-i]、Y[n-i+1..n] 是好的 ab-words，且
     X[1..i] 与 Y[n-i+1..n] 相似，X[i+1..n] 与 Y[1..n-i] 相似。

一个好的 ab-words 的非空集合 S 的 多样性的水平（diversity level） 定义为：
在 S 中最多能选出的 ab-words 的个数，使得选出的任意一对 w1、w2 都满足 w1 不相似于 w2。

Input Format

写出以下一个程序：

• 读入集合 S；
• 计算集合 S 的多样性的水平。

输入文件第一行是集合 S 的元素个数 n（1 <= n <= 1000）。
接下来 n 行，每行一个 ab-word（仅由 a、b 组成）。每个 ab-word 的首字母是该行的首字符，两个连续字母之间没有空格。
每个 ab-word 的长度是 [1..200] 范围内的整数。

Sample

Input

3
aabaabbbab
abababaabb
abaaabbabb

Output

2