Find the maximum string factor number among all possible subsets of N strings (each string containing only 'x' and/or 'y'). Here, String factor of 'x' number of strings = x*(Longest common prefix of x strings) .

Input Format:-

First line contains t (number ot test cases).

Next line contains N (number of strings) followed by N strings each in a new line.

Output Format:-

Output the required number in a new line.

Constraints:-

1<=t<=10

1<=N<=8000

Length of each string doesn't exceed 200.

Problem Setter:-

Ashish Jha