Description

采矿时，一块矿石含有多种成分。如果矿石的成分越少，则纯度越高。今用字串表示矿石，字串的长度表示对矿石的测量次数，字串不同的字符种类表示成分的种数。测量次数一定，测出的成分数越少，则会优先考虑试采。

Input

测试分组，每组第一个是整数n，表示后面有n个已经测试过的矿石样本。如果遇到0，表示输入结束。

Output

对于每组数据，按纯度的好坏排列，如果纯度一样，则按长度从小到大排列，如果长度再一样，则按字典序排列。每个矿石样本占一行。每组数据之间空一行。

Sample

Input

3
asdfds
ewrewrt
ert
2
www
aaa
0

Output

ewrewrt
asdfds
ert

aaa
www

Source: qianeng