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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class hacker49 {

	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
	static long[] x= {1,1,1,0,0,0,-1,-1,-1};
	static long[] y= {1,-1,0,-1,0,1,1,-1,0};
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
	int t=s.nextInt();
	while(t>0) {
      int n=s.nextInt();
      pair[] a=new pair[n];
      pair[] b=new pair[n];
      pair[] c=new pair[n];
      pair[] d=new pair[n];
      pair[] e=new pair[n]; 
		for(int i=0;i<n;i++) {
			String str=s.next();
			long c1=0;
			long c2=0;
			long c3=0;
			long c4=0;
			long c5=0;
			long k=str.length();
			for(int j=0;j<k;j++) {
				if(str.charAt(j)=='a') {
					c1++;
				}else if(str.charAt(j)=='b') {
					c2++;
				}else if(str.charAt(j)=='c') {
					c3++;
				}else if(str.charAt(j)=='d') {
					c4++;
				}else {
					c5++;
				}
			}
			a[i]=new pair(c1,k);
			b[i]=new pair(c2,k);
			c[i]=new pair(c3,k);
			d[i]=new pair(c4,k);
			e[i]=new pair(c5,k);
		}
		sf(a);
		sf(b);
		sf(c);
		sf(d);
		sf(e);
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		Arrays.sort(d);
		Arrays.sort(e);
		long ans=Long.MIN_VALUE;
		long d1=0;
		long d2=0;
		for(int i=0;i<n;i++) {
			d1+=a[i].a;
			d2+=a[i].b;
			long p=d2-d1
					;
//			System.out.println(d1+" "+d2);
			if(d1>p) {
				ans=Math.max(i+1, ans);
			}
		}
		long f=d2-d1;
//		System.out.println(d1+" "+d2);
		if(d1>f) {
			ans=Math.max(n, ans);
		}
//   out.println(ans);
		d1=0;
		d2=0;
		for(int i=0;i<n;i++) {
			d1+=b[i].a;
			d2+=b[i].b;
			long p=d2-d1;
			if(d1>p) {
				ans=Math.max(i+1, ans);
			}
		}
		 f=d2-d1;
		if(d1>f) {
			ans=Math.max(n, ans);
		}
		d1=0;
		d2=0;
//		out.println(ans);
		for(int i=0;i<n;i++) {
			d1+=c[i].a;
			d2+=c[i].b;
			long p=d2-d1;
			if(d1>p) {
				ans=Math.max(i+1, ans);
			}
		}
		 f=d2-d1;
		if(f<d1) {
			ans=Math.max(n, ans);
		}
		d1=0;
		d2=0;
//		out.println(ans);
		for(int i=0;i<n;i++) {
			d1+=d[i].a;
			d2+=d[i].b;
			long p=d2-d1;
			if(d1>p) {
				ans=Math.max(i+1, ans);
			}
		}
		f=d2-d1;
		if(f<d1) {
			ans=Math.max(n, ans);
		}
		d1=0;
		d2=0;
//		out.println(ans);
		for(int i=0;i<n;i++) {
			d1+=e[i].a;
			d2+=e[i].b;
			long p=d2-d1;
			if(d1>p) {
				ans=Math.max(i+1, ans);
			}
		}
		 f=d2-d1;
		if(d1>f) {
			ans=Math.max(n, ans);
		}
		out.println(ans!=Long.MIN_VALUE?ans:0);
      t--;
	}
			out.close();
	}
	
static long m=-1;
static void sf(pair[] arr){
        int n = arr.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            pair tmp = arr[i];
            int randomPos = i + rnd.nextInt(n-i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }   
}
	
static HashMap<Integer,pair> e=new HashMap<>();
static ArrayList<Integer>[] f1=new ArrayList[200001];	
static PriorityQueue<pair> q=new PriorityQueue<>();	
static ArrayList<pair>[] f=new ArrayList[200001];
	static class pair implements Comparable<pair>{
		private long a;
		private long b;
		pair(long a,long b){
			this.a=a;
			this.b=b;
		}
		public int compareTo(pair o) {
//			if(o.a!=this.a) {
//			return Integer.compare(o.a, this.a);}else {
//			if(this.b-this.a ==o.b-o.a) {
//				return Long.compare(o.a, this.a);
//			}
				return Double.compare(2*o.a-o.b,2*this.a-this.b);
//			}
		}
//		
		
	}
	static class node{
		private int a;
		private int b;
		node(int a,int b){
			this.a=a;
			this.b=b;
		}
	}
static int[] col=new int[200001];
static int[] subtree=new int[200001];
static int[] vis=new int[200001];
static int dfs(int node) {
		vis[node]=1;
		int c=0;
		for(int i=0;i<f[node].size();i++) {
//			if(vis[f[node].get(i).a]==0) {
//				c+=dfs(f[node].get(i).a);
//			}
		}
		subtree[node]+=c;
		subtree[node]+=col[node];
		return subtree[node];
	}
	public static int upper_bound(long[] a ,long x,int n) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return r;
				
	}
	public static int lower_bound(long[] a ,long x,int n) {
		int l=-1;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	public static long lb(int n,long[] pre,long k,long a,long b,long x,long y) {
		long l=0;
		long r=n+1;
		while(l<r) {
			long mid=(l+r)/2;
			long sum=0;
			long gcd=GCD(a,b);
			long g=mid/(a*b/gcd);
			long a1=mid/a;
			long b1=mid/b;
			sum+=(pre[(int) g]*(x+y))/100;
			if(x>=y) {
				sum+=((pre[(int) a1]-pre[(int) g])*x)/100;
				sum+=(((pre[(int)(a1+b1-g)]-pre[(int)(a1)])*y))/100;
			}else {
				sum+=((pre[(int) b1]-pre[(int) g])*y)/100;
				sum+=(((pre[(int)(a1+b1-g)]-pre[(int)(b1)])*x))/100;
			}
			if(sum>=k) {
				r=mid;
			}else {
				l=mid+1;
			}
//			System.out.println(mid+" "+h);
		}
		
		return r;
				
	}
	
	
	
	public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
		
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] < b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}	
	public static int[] Create(int[] a,int n) {
		int[] b=new int[n+1];
		for(int i=1;i<=n;i++) {
			int j=i;
			int h=a[i];
			while(i<=n) {
				b[i]+=h;
				i=get_next(i);
			}
			i=j;
		}
		return b;
	}
public static int get_next(int a) {
	return a+(a&-a);
}
public static int get_parent(int a) {
	return a-(a&-a);
}
public static int query_1(int[] b,int index) {
	int sum=0;
	if(index<=0) {
		return 0;
	}
	while(index>0) {
		sum+=b[index];
		index=get_parent(index);
	}
	return sum;
}
public static int query(int[] b,int n,int l,int r) {
	int sum=0;
	sum+=query_1(b,r);
	sum-=query_1(b,l-1);
	return sum;
}
public static void update(int[] a,int[] b,int n,int index,int val) {
	int diff=val-a[index];
	a[index]+=diff;
	while(index<=n) {
		b[index]+=diff;
		index=get_next(index);
	}	
}
	
//	public static void Create(int[] a,pair[] segtree,int low,int high,int pos) {
//		if(low>high) {
//			return;
//		}
//		if(low==high) {
//			segtree[pos].b.add(a[low]);
//			return ;
//		}
//		int mid=(low+high)/2;
//		Create(a,segtree,low,mid,2*pos);
//		Create(a,segtree,mid+1,high,2*pos+1);
//		segtree[pos].b.addAll(segtree[2*pos].b);
//		segtree[pos].b.addAll(segtree[2*pos+1].b);
//	}
//	public static void update(pair[] segtree,int low,int high,int index,int pos,int val,int prev) {
//		if(index>high || index<low) {
//			return ;
//		}
//		if(low==high && low==index) {
//			segtree[pos].b.remove(prev);
//			segtree[pos].b.add(val);
//			return;
//		}
//			int mid=(high+low)/2;
//			 update(segtree,low,mid,index,2*pos,val,prev);
//			 update(segtree,mid+1,high,index,2*pos+1,val,prev);
//			 segtree[pos].b.clear();
//			  segtree[pos].b.addAll(segtree[2*pos].b);
//			  segtree[pos].b.addAll(segtree[2*pos+1].b);
//			  
//	}
//	public static pair query(pair[] segtree,int low,int high,int qlow,int qhigh ,int pos) {
//		if(low>=qlow && high<=qhigh) {
//			return segtree[pos];
//		}
//		if(qhigh<low || qlow>high) {
//			return new pair();
//		}
//		int mid=(low+high)/2;
//	  pair a1=query(segtree,low,mid,qlow,qhigh,2*pos);
//	  pair a2=query(segtree,mid+1,high,qlow,qhigh,2*pos+1);
//	  pair a3=new pair();
//	  a3.b.addAll(a1.b);
//	  a3.b.addAll(a2.b);
//	  return a3;
//	  
//	}
//	
//	public static int nextPowerOf2(int n) 
//	{ 
//	    n--; 
//	    n |= n >> 1; 
//	    n |= n >> 2; 
//	    n |= n >> 4; 
//	    n |= n >> 8; 
//	    n |= n >> 16; 
//	    n++;     
//	    return n; 
//	} 
//	
////	static class pair implements Comparable<pair>{
////		private int a;
////		private long b;
//////		private long c;
////		pair(int a,long b){
////			this.a=a;
////			this.b=b;
//////			this.c=c;
////		}
////		public int compareTo(pair o) {
//////		if(this.a!=o.a) {
//////			return Long.compare(this.a, o.a);
//////		}else {
////			return Long.compare(o.b,this.b);
//////		}
////		}
////	}
//	static class pair implements Comparable<pair>{
//		private int a;
//		private int b;
//		pair(int a,int b){
////			this.b=new HashSet<>();
//			this.a=a;
//			this.b=b;
//		}
//		public int compareTo(pair o) {
//			return Integer.compare(this.b, o.b);
//		}
//	}
	public static int lower_bound(ArrayList<Long> a ,int n,long x) {
		int l=0;
		int r=n;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a.get(mid)<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;		
	}
	public static int[] is_prime=new int[1000001];
	public static ArrayList<Long> primes=new ArrayList<>();
 	public static void sieve() {
		long maxN=1000000;
		for(long i=1;i<=maxN;i++) {
			is_prime[(int) i]=1;
		}
		is_prime[0]=0;
		is_prime[1]=0;
		for(long i=2;i*i<=maxN;i++) {
			if(is_prime[(int) i]==1) {
//				primes.add((int) i);
				for(long j=i*i;j<=maxN;j+=i) {
					is_prime[(int) j]=0;
				}
			}
		}
		for(long i=0;i<=maxN;i++) {
			if(is_prime[(int) i]==1) {
				primes.add(i);
			}
		}		
	}
//	public static pair[] merge_sort(pair[] A, int start, int end) {
//		if (end > start) {
//			int mid = (end + start) / 2;
//			pair[] v = merge_sort(A, start, mid);
//			pair[] o = merge_sort(A, mid + 1, end);
//			return (merge(v, o));
//		} else {
//			pair[] y = new pair[1];
//			y[0] = A[start];
//			return y;
//		}
//	}
//	public static pair[] merge(pair a[], pair b[]) {
//		pair[] temp = new pair[a.length + b.length];
//		int m = a.length;
//		int n = b.length;
//		int i = 0;
//		int j = 0;
//		int c = 0;
//		while (i < m && j < n) {
//			if (a[i].b >= b[j].b) {
//				temp[c++] = a[i++];
//			
//			} else {
//				temp[c++] = b[j++];
//			}
//		}
//		while (i < m) {
//			temp[c++] = a[i++];
//		}
//		while (j < n) {
//			temp[c++] = b[j++];
//		}
//		return temp;
//	}
	public static long im(long a) {
		return binary_exponentiation_1(a,mod-2)%mod;
	}
	public static long binary_exponentiation_1(long a,long n) {
		long res=1;
		while(n>0) {
			if(n%2!=0) {
				res=((res)%(mod) * (a)%(mod))%(mod);
				n--;
			}else {
				a=((a)%(mod) *(a)%(mod))%(mod);
				n/=2;
			}
		}
		return (res)%(mod);
		
	}

	public static double bn1(double a,double n) {
		double res=1;
		while(n>0) {
			if(n%2!=0) {
//				res=((res)%(1000000007) * (a)%(1000000007))%(1000000007);
				res=(res*a);
				n--;
			}else {
//				a=((a)%(1000000007) *(a)%(1000000007))%(1000000007);
				a=(a*a);
				n/=2;
			}
		}
		return (res);	
	}
	public static long bn(long a,long n) {
		long res=1;
		while(n>0) {
			if(n%2!=0) {
				res=res*a;
				n--;
			}else {
				a*=a;
				n/=2;
			}
		}
		return res;
		
	}
public static long[] fac=new long[300001];
public static void ff() {
		fac[0]=(long)1;
		fac[1]=(long)1;
		for(long i=2;i<=300000;i++) {
			fac[(int) i]=(fac[(int) (i-1)]*i)%(m);
		}
	}	
public static long mod=998244353;
public static long GCD(long a,long b) {
		if(b==(long)0) {
			return a;
		}
		return GCD(b , a%b);
	}
public static long c=0;	
}