题目描述

对于一个字符串，定义它的前缀就是指字符串的任意首部。例如字符串abcdefg的前缀有空串，abcdefg，abcdeg，abcde等等。
现在有n个字符串，那么他们所有的前缀中，出现次数最多的前缀是什么呢（当然忽略空串的出现）?

输入要求

第一行输入一个T（1<=T<=200）代表有T组测试数据
对于每组测试数据
第一行输入一个n，代表有n个字符串（1<=n<=1000）
接下来n行，每行一个字符串(保证字符串内只有数字与小写字母且不为空串，字符串长度小于等于1000)

输出要求

对于第t组数据，
第一行输出首先输出“Case t:“
第二行输出一个字符串，表示出现次数最多的前缀。（若有多个符合题意的字符串，则输出字典序最小的那个）

输入样例

1
3
a
ab
cde

输出样例

Case 1:
a

提示

来源

NBU KissM