human
Stephen Queen wants to write a story. He is a very unusual writer, he uses only letters 'a', 'b', 'c', 'd' and 'e'!

To compose a story, Stephen wrote out n words consisting of the first 5 lowercase letters of the Latin alphabet. He wants to select the maximum number of words to make an interesting story.

Let a story be a sequence of words that are not necessarily different. A story is called interesting if there exists a letter which occurs among all words of the story more times than all other letters together.

For example, the story consisting of three words "bac", "aaada", "e" is interesting (the letter 'a' occurs 5 times, all other letters occur 4 times in total). But the story consisting of two words "aba", "abcde" is not (no such letter that it occurs more than all other letters in total).

You are given a sequence of n words consisting of letters 'a', 'b', 'c', 'd' and 'e'. Your task is to choose the maximum number of them to make an interesting story. If there's no way to make a non-empty story, output 0.

Input

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

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 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 ⋅ 10^5.
the sum of the lengths of all words over all test cases doesn't exceed 4 ⋅ 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.

Example

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

Output

3
2
0
2
3
2

Note

In the first test case of the example, all 3 words...
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to print 0 if there's no way to make a non-empty interesting story.

import bisect
import math
import collections
import sys
import copy
from functools import reduce
import decimal

sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict
queue = collections.deque

class Graphs:
    def __init__(self):
        self.graph = graphDict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)
            else:
                return neighbour

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(node, Visited)

    def bfs(self, node):
        visited = set()
        if node not in visited:
            queue.append(node)
            visited.add(node)
        while queue:
            parent = queue.popleft()
            print(parent)
            for item in self.graph[parent]:
                if item not in visited:
                    queue.append(item)
                    visited.add(item)

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def inp():
    return sys.stdin.readline().strip()

def map_inp(v_type):
    return map(v_type, inp().split())

def list_inp(v_type):
    return list(map_inp(v_type))

######################################## Solution ####################################

for _ in range(int(inp())):
    n = int(inp())
    dic = {"a": [], "b": [], "c": [], "d": [], "e": []}
    for i in range(n):
        s = inp()
        freq = collections.Counter(s)
        for item in dic:
            if item in freq:
                dic[item].append(2*freq[item] - len(s))
            else:
                dic[item].append(0 - len(s))
    for item in dic:
       ...