题目描述

对字符串的处理与操作是程序设计中永恒的主题之一，也是一项很重要的基本功。你对字符串熟悉吗？ 给你 $n（1≤n≤20）$ 个字符串（ $1 ≤$ 字符串长度 $≤ 2000$），所有的字符串中最多包含 'A' 到 'N' 这 $14$ 种大写字母。从中选取若干个字符串，使得被选取的字符串中出现的每种字母总数均为偶数，请编程计算最多可以选取多少个字符串？

输入格式

输入共 $n+1$ 行

第 $1$ 行一个整数 $n$，表示共有多少个字符串。

接下来 $n$ 行，每行一个无序的字符串，字符串中最多包含 'A' 到 'N' 这 $14$ 种大写字母（不考虑行末回车等不可见的字符）。

输出格式

输出共 $1$ 行，表示最多可以选取的字符串数目。

样例

2
A
AD

0

3
AD
AD
AB

2

5
AD
A
BA
B
D

4

提示

【样例 $1$ 解释】

输入样例 $1$ 中的 $2$ 个字符串不管如何选择都不能保证每种字母加起来都是偶数。

【样例 $2$ 解释】

选取输入中的两个“AD”字符串，使得 $A$ 有 $2$ 个， $D$ 也有 $2$ 个，都是偶数。

【样例 $3$ 解释】

选取“A”、“BA“、“B” $3$ 个字符串能使 $A$ 和 $B$ 的个数都为偶数，但选取的字符串个数仅为 $3$，不是最多。选取输入中的“AD”、“BA”、“B”、“D” $4$个字符串，使得 $A、B、D$ 的总个数为偶数且选取的字符串总数为 $4$ ，满足个数最多。

【数据范围】

对于 $50\%$ 的数据，$1≤n≤15，1≤$ 字符串长度 $≤200$ ，且字符串中最多包含‘A’到‘G’ 7种不同的字母。

对于 $100\%$ 的数据，$1≤n≤20，1≤$ 字符串长度 $≤2000$，且字符串中最多包含‘A’到‘N’ $14$种不同的字母。