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 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".
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.util.*;
import java.io.*;

public class C
{
    static int n;
    static int[] arr;
    static char[][] s;
    public static void main(String[] args) throws IOException
    {
        f = new Flash();
        out = new PrintWriter(System.out);
        
        int T = ni();
        for(int tc = 1; tc <= T; tc++){
        	n = ni(); s = new char[n][];
        	for(int i = 0; i < n; i++) {
        		s[i] = nc();
        	}
        	
        	sop(fn());
        }
        
        out.flush(); out.close();
    }
    
    static int fn()
    {
        int ans = 0;
        for(char c = 'a'; c <= 'e'; c++) {
        	ans = max(ans, solve(s, c));
        }
        
        return ans;
    }
    
    static int solve(char[][] s, char c) {
    	PriorityQueue<int[]> q = new PriorityQueue<>(new cpr());
    	long totalother = 0, totalc = 0;
    	for(int i = 0; i < n; i++) {
    		int cntc = 0;
    		for(char a : s[i]) {
    			if(a == c) cntc++;
    		}
    		
    		int other = s[i].length-cntc;
    		int diff = other-cntc;
    		q.add(new int[] {diff, other, cntc, s[i].length});
    		totalother += other;
    		totalc += cntc;
    	}
    	
    	if(totalc > totalother) return n;
    	int len = n;
    	while(!q.isEmpty()) {
    		int[] arr = q.poll();
    		totalother -= arr[1];
    		totalc -= arr[2];
    		len -= 1;
    		if(totalc > totalother) return len;
    	}
    	
    	return 0;
    }
    
    static Flash f;
    static PrintWriter out;
    static final long mod = (long)1e9+7;
    static final long inf = (long)1e18;
    static final int _inf = (int)1e9;
    static final int maxN = (int)1e6;
    static long[] fact, inv;
    
    static class cpr implements Comparator<int[]>{
    	public int compare(int[] a, int[] b) {
    		if(a[0] == b[0]) {
    			if(a[1] == b[1]) return Integer.compare(a[2], b[2]);
    			return Integer.compare(b[1], b[1]);
    		}
    		return Integer.compare(b[0], a[0]);
    	}
    }
    
    static void sort(int[] a){
        List<Integer> A = new ArrayList<>();
        for(int i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void sort(long[] a){
        List<Long> A = new ArrayList<>();
        for(long i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void print(int[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static void print(long[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static int swap(int itself, int dummy){return itself;}
    static long swap(long itself, long dummy){return itself;}
    static char swap(char itself, char dummy){return itself;}
    static void sop(Object o){out.println(o);}
    static int ni(){return f.ni();}
    static long nl(){return f.nl();}
    static double nd(){return f.nd();}
    static String next(){return f.next();}
    static String ns(){return f.ns();}
    static String yes = "YES", no = "NO";
    static char[] nc(){return f.nc();}
    static int[] arr(int len){return f.arr(len);}
    static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
    static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
    static int fcm(int a, int b){return (a*b)/gcd(a, b);}
    static long fcm(long a, long b){return (a*b)/gcd(a, b);}
    static double log2(long N) {return Math.log(N) / Math.log(2);}
    static void debug(int[] a) {sop(Arrays.toString(a));}
    static void debug(long[] a) {sop(Arrays.toString(a));}
    
    static class Flash
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next(){
            while(!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        String ns(){
            String s = new String();
            try{
                s = br.readLine().trim();
            }catch(IOException e){
                e.printStackTrace();
            }
            
            return s;
        }
        
        int[] arr(int n){
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = ni();
            return a;
        }
        
        char[] nc(){return ns().toCharArray();}
        int ni(){return Integer.parseInt(next());}
        long nl(){return Long.parseLong(next());}
        double nd(){return Double.parseDouble(next());}
    }
}