11451145 SUSTech Online Judge
Problem 1145 --SkrSkr! [Easy]

1145: SkrSkr! [Easy]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 553  Solved: 245
[Submit][Status][Web Board]

Description

Hong likes the Rap of China. He has tried to write some lyrics. However, he didn’t know how to judge a lyric. He thought that the more rhymes the better. The score of a lyric is equal to the length of the longest continued rhyming sentences.  Two sentences are rhyming when the last letters of them are equal.  Hong wants to know the score of the given lyrics.

Input

The first line will be an integer T (1≤T≤100), which is the number of test cases.  

For each test data:

The first line contains an integer N (1≤N≤10^4) — the number of the sentences.

Each of the next N lines contains a string s, which consists only of lowercase letters (no space). The length of each string doesn’t exceed 100.

Output

For each case please, print the length of the longest continued rhyming sentences.

Sample Input

1
5
nikanzhegemian
tayouchangyoukuan
jiuxiangzhegewan
tayoudayouyuan
skrskr

Sample Output

4

HINT

Source

[Submit][Status]