Interesting Story

Description:

Input:

The first line contains one integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of the words in the sequence. Then $$$n$$$ lines follow, each of them contains a word — a non-empty string consisting of lowercase letters of the Latin alphabet. The words in the sequence may be non-distinct (i. e. duplicates are allowed). Only the letters 'a', 'b', 'c', 'd' and 'e' may occur in the words.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$; the sum of the lengths of all words over all test cases doesn't exceed $$$4 \cdot 10^5$$$.

Output:

For each test case, output the maximum number of words that compose an interesting story. Print 0 if there's no way to make a non-empty interesting story.

Sample Input:

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

Sample Output:

3
2
0
2
3
2

Note:

In the first test case of the example, all $$$3$$$ words can be used to make an interesting story. The interesting story is "bac aaada e".

In the second test case of the example, the $$$1$$$-st and the $$$3$$$-rd words can be used to make an interesting story. The interesting story is "aba aba". Stephen can't use all three words at the same time.

In the third test case of the example, Stephen can't make a non-empty interesting story. So the answer is $$$0$$$.

In the fourth test case of the example, Stephen can use the $$$3$$$-rd and the $$$4$$$-th words to make an interesting story. The interesting story is "c bc".