题目描述

最近情报人员得到了一些经过加密的文章，每个单词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前缀，但所取的前缀不能是其它单词的前缀。 
这个任务现在就交给你来完成。 
解释：“字符串s1是s2的前缀”是说把字符串s2的后面去掉某些，只保留与s1相同长度时，s2就与s1完全相同。如："abc"是"abcaade"和"abc"的前缀，但不是"ababc"的前缀。 

Input

第一行一个整数N，表示单词个数。 
下面有N行，每行一个单词。 

Output

共N行，每行一个单词，是对应上面的N个单词的化简后的单词。 

Sample Input

输入一
3
abc
efg
ijh 
输入二
3
aac
aad
aae

Sample Output

输出一
a
e
i 
输出二
aac
aad
aae

Hint

单词数N，1<=N<=50； 每个单词长度不超过50；并且单词都由小写字母构成。 
保证所给单词没有一个单词是另一个单词的前缀。