You and your friend are playing a numbers game. The rules of the game are simple. On a given string S containing only digits, the first player thinks of a target number T and the second player needs to locate that number in S. If the second player can't locate the number, the first player wins. Now it's your time to think of a number.

Because you are very smart and you always want to win, think of a smallest target number T, which is not a substring of S. You will win every time! :)

Input

The first line is an integer T (1 <= T <= 100) number of test cases, followed by T lines with one string S in each line that contains only the digits 0-9. S will contain less than 1 000 000 (one milion) digits.

Output

Print the smallest target number T that is not a substring of S.

Constraints

Time limit: 4 seconds
Memory limit: 64 megabytes

Examples

input
3
1023456789
1023479
112131405678910

output
11
5
15