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.
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.
For each case please, print the length of the longest continued rhyming sentences.
1
5
nikanzhegemian
tayouchangyoukuan
jiuxiangzhegewan
tayoudayouyuan
skrskr
4