Problem Statement
Peter wants to a participate in the “Unico Contest - 2014”. In the contest, he will be given a long string and he has to find the longest sub-string with no repeating characters in it. If there are two sub-strings of equal length, then the first found string is the answer. Can you help Peter win the contest?

Input
First line consists of an integer t, denoting the number of testcases. After that exactly t lines follow, each containing a string containing only upper case English language alphabets.

Output
For each test case, print the longest substring without repeating characters.

Constraints
1 <= t <= 100
1 <= n <= 10 ^ 6

Sample Input
1
ABCDEFGHIJKKLMNOPQRSTU

Sample Output
ABCDEFGHIJK

Explanation
ABCDEFGHIJK is the first string found with no repeating characters