题目描述

英语练习册里有 n 个单词，每个单词都是由小写英文字母构成的。小明从这 n 个单词中挑选了若干个单词，并抄写到了白纸上。

小明计算了他总共抄写了多少个字母（记为 x ）。

然后小明还统计了他写下的那些单词当中，哪个字母出现的次数最多，记录出现次数最多的那个字母的出现次数为 y ，如果 y>x/2 ，那么这个字母就是 “字母王” ；如果 y<=x/2 ，那么小明就认为他的白纸上没有“字母王”。

小明的目标是： 尽量多的抄写单词到白纸上，同时要满足白纸上存在“字母王”，那么小明最多可以抄写多少个单词？

输入格式

多组测试数据。

第一行，一个整数 G ，表示有 G 组测试数据 ( 1 <= G <= 100000 )。

每组测试数据格式如下：

第 1 行，一个整数 n ( 1 <= n <= 100000 )。

第 2 行， n 个单词，每个单词长度不超过 15 ，而且单词只包含 5 种小写英文字母：'a'、'b'、'c'、'd'、'e'。

数据保证：对于所有的 G 组测试数据， n 的总和不超过 200000 。

输出格式

共 G 行，每行一个整数，如果无论如何抄写单词都不存在“字母王” ，输出 0 。

样例

6
3
bac
aaada
e
3
aba
abcde
aba
2
baba
baba
4
ab
ab
c
bc
5
cbdca
d
a
d
e
3
b
c
ca

3
2
0
2
3
2