Problem : 179 - 爆炸的期中考

Problem Statistics

Solved Member: 24　　Submission: 61　　User Tried: 24

Statement:

有一天，hh國國王Seven One Two Two For Life命令史記官整理王族歷屆來的祖譜。如你所見hh國國王的名字非常長，這是歷屆以來的傳統，也是國家強大的秘方，這讓史記官十分的苦惱，因為這樣記錄起來十分的不方便，所以史記官總是會為這些名字長的國王縮寫！縮短的方法是只取出所有的第一個字母，他便會變成SOTTFL，既不失王者風範，也可以方便紀載hh國的歷史。

hh國的歷史非常長，根據王國的傳統，繼承者的首名，必須跟前任國王的尾名一樣，因此在史記官的神奇縮寫下，你會發現繼承者的開頭字母會與前任國王的結尾字母一樣。

難過的是，再強大的王國也有滅亡的一天，傳說，在隕石砸落後，hh國便滅亡了...

身為hh國的後裔hanhan，聰明的找到自己的祖譜，打算將所有名字串起來，並將其取為新名字，此時hanhan意外的發現，hh國第一任國王的第一個字母，與最後一任國王的最後一任字母一樣(縮寫後)，並在其中找出了一翻奧妙，開了一門The name of HanHan's Dynasty Algorithm。

在數十年後，hanhan也因此成名，現在你正在期中考，hanhan依照年份給了你一堆國王與親屬的名字，根據他祖先的命名方法，你要從裡面選出一些名字做為歷屆國王，問此新名字最長可能為多長。

Input:Output:

第一個數字T代表你有T題題目要寫。每題題目的第一個數字n(1≤n≤500000)代表全部有多少個名字，接下來有n行，每行有一個字串Si，代表按照時間點所寫下來的名字，其中名字的長度不會超過十個字元，且全為小寫字母。

對於每一題題目輸出一個數字代表此王國的歷屆名字最長的可能長度。若hh國並不存在，請輸出0。

Sample Input:Sample Output:

3
3
abc
ca
cba
4
vvp
vvp
dam
vvp
3
ab
c
def

6
0
1

HINT:

題目1:"abccba"比"abcca"還長

題目2:不可能存在hh王朝

題目3:只有一個國王，名字是"c"

Source:

Codeforces #121

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	500ms	131072kb
1-1	500ms	131072kb	10
1-2	500ms	131072kb
1-3	500ms	131072kb
2-1	500ms	131072kb	10
2-2	500ms	131072kb
2-3	500ms	131072kb
3-1	700ms	131072kb	10
3-2	700ms	131072kb
3-3	700ms	131072kb
4-1	700ms	131072kb	10
4-2	700ms	131072kb
4-3	700ms	131072kb
5-1	700ms	131072kb	10
5-2	700ms	131072kb
5-3	700ms	131072kb
6-1	700ms	131072kb	10
6-2	700ms	131072kb
6-3	700ms	131072kb
7-1	1000ms	131072kb	10
7-2	1000ms	131072kb
7-3	1000ms	131072kb
8-1	3000ms	131072kb	10
8-2	3000ms	131072kb
8-3	3000ms	131072kb
9-1	4000ms	131072kb	10
9-2	4000ms	131072kb
9-3	4000ms	131072kb
10-1	5000ms	131072kb	10
10-2	5000ms	131072kb
10-3	5000ms	131072kb