Shortest Unique Prefix

You are given an array containing ‘N’ words. For each word, you need to find its shortest prefix which can uniquely identify it. For example “abcd” and “abdc” both have the prefix “ab” in common so we can’t uniquely find a word using the prefix “ab”. To uniquely identify both the words we need the prefix “abc” from “abcd” and “abd” from “abdc”.

Note:

You can assume that the words are unique. It means that it is always possible to find a unique prefix for each word.

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines describe the ‘T’ test cases.

The first line of each test case contains single positive integers ‘N’ denoting the number of words.
The next ‘N’ lines contain a string of lower case characters.

Output Format:

The output of each test case should contain 'N' lines, in the ith line you need to print the shortest unique prefix for ith word.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4  

Where ‘T’ is the number of test cases, ‘N’ is the number of words and, the sum of the lengths of all the words in a test case is less than 10^4.

Time Limit: 1 sec