Description

Recently, intelligence officers obtained some encrypted articles, and every word is very long. The codebreakers want to simplify the words first. The method is to take, for each word, the shortest possible prefix, but the chosen prefix must not be a prefix of any other word.

This task is now assigned to you.

Explanation: “String $\text{S}_1$ is a prefix of $\text{S}_2$” means that if you delete some characters from the end of string $\text{S}_2$ and keep only the part with the same length as $\text{S}_1$, then $\text{S}_2$ becomes exactly the same as $\text{S}_1$. For example, $\texttt{abc}$ is a prefix of $\texttt{abcaade}$ and $\texttt{abc}$, but it is not a prefix of $\texttt{abadc}$.

Input Format

The first line contains an integer $N$, representing the number of words.

The following $N$ lines each contain one word.

Output Format

Output $N$ lines, each containing one word, which is the simplified version of the corresponding word above.

3   
abc 
efg 
ijh

a
e
i

3
aac
aad
aae

aac
aad
aae

Hint

For $100\%$ of the testdata, $1 \le N \le 50$, each word has length at most $50$, and all words consist of lowercase letters.

It is guaranteed that none of the given words is a prefix of another word.

Translated by ChatGPT 5