Every sequence of small letters a and b (also the empty sequence) is called an ab-word. If X = [x₁, ..., x_n] is an ab-word and i, j are integers such that 1 <= i <= j <= n then X[i..j] denotes the subword of X consisting of the letters x_i, ..., x_j. We say that an ab-word X = [x₁..x_n] is nice if it has as many letters a as b and for all i = 1, ..., n the subword X[1..i] has at least as many letters a as b.

Now, we give the inductive definition of the similarity between nice ab-words.

A level of diversity of a non-empty set S of nice ab-words is the maximal number of ab-words that can be chosen from S in such a way that for each pair w₁,w₂ of chosen words, w₁ is not similar to w₂.

Task

Write a program that for each test case:

Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.

In the first line of a test case there is a number n of elements of the set S, 1 <= n <= 1000; in the following n lines there are elements of the set S, i.e. nice ab-words (one word in each line); the first letter of every ab-word is the first symbol in line and there are no spaces between two consecutive letters in the word; the length of every ab-word is an integer from the range [1..200].

Output

For each test case your program should output one line with one integer - the level of diversity of S.

Example

Sample input:
1
3
aabaabbbab
abababaabb
abaaabbabb

Sample output:
2