Suppose in a list of n distinct words, no word is a prefix of another word. In that case, each word has a unique prefix too, often shorter than word, which can be used to distinctly represent the word among the list of n words. Find out the shortest unique prefix of each word.

Input Format:
Input starts with a positive integer n indicating the number of words to follow, one in each line. A word in each line n lines.

Output Format:
Output to have n lines, one line for each corresponding input word, with the shortest prefix of the word.

Constraints:
1 ≤ n ≤ 10^6
1 ≤ length of word ≤ 10^3
1 ≤ sum of the number of characters of all the words ≤ 10^6