描述

英语练习册里有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

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