Mix and Build

Time Limit: 5 Seconds    Memory Limit: 32768 KB
Special Judge

In this problem, you are given a list of words (sequence of lower case letters). From this list, find the longest chain of words w₁, ..., w_n such that w_i is a mixed extension of w_i-1. A word A is a mixed extension of another word B if A can be formed by adding one letter to B and permuting the result. For example, "ab", "bar", "crab", "cobra", and "carbon" form a chain of length 5.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Input

Each input block contains at least two, but no more than 10000 lines. Each line contains a word. The length of each word is at least 1 and no more than 20. All words in the input are distinct.

Output

Write the longest chain that can be constructed from the given words. Output each word in the chain on a separate line, starting from the first one. If there are multiple longest chains, any longest chain is acceptable.

Sample Input

1

ab
arc
arco
bar
bran
carbon
carbons
cobra
crab
crayon
narc

Sample Output

ab
bar
crab
cobra
carbon
carbons

Submit

Source: Rocky Mountain 2004