I. A Movie in Byteland
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There are two ways of reading names in Byteland. Either from left to right, or from right to left. For example, if a person called "mike" went to Byteland, the citizens might call him "mike" or "ekim".

Feras is the Casting Director for a new movie. There are N actors in Byteland, and he has to choose some of them to act in the new movie.

Feras knows that all of the actors are good, so he is only worried about what order he is going to use in the list of chosen actors.

An actor i would be disappointed if another actor j was listed before him, while actor i has a lexicographically smaller name in any of the two ways mentioned above. In other words, he will be disappointed if actor j was listed before actor i in the final list and siltr < sjltr or sirtl < sjrtl.

siltr is the name of actor i written from left to right.

sirtl is the name of actor j written from right to left.

Feras wants to choose the maximum number of actors possible such that there exists a way to order them so that none of them would be disappointed. In addition, he wants that in each pair of consecutive names on the list, exactly one of them contains the letter "m" . (His crush's name has too many letters "m" and he wants to remember her while producing the movie)

Input

The first line contains an integer T, the number of test cases.

The first line of each test contains the number of actors N. (1 ≤ N ≤ 105)

Then N lines follow, the ith line contains the name of the ith actor written from left to right, the name consists of lowercase english letters. (1 ≤ |si| ≤ 105). It's guaranteed that the sum of the lengths of all the names in each test case will not exceed 106

Output

For each test print one line containing one integer, the maximum possible number of actors Feras can choose while keeping him and all the chosen actors happy.

Example
Input
2
3
aaa
ama
aza
3
abcdef
bcmde
cd
Output
3
1
Note

Large I/O files. Please consider using fast input/output methods.