You are given string S. Find lexicographically smallest string, that is not subsequence of given string. Subsequence of string is created by deleting zero or more characters from starting string.

Subsequences of string "abc" are { "a", "b", "c", "ab", "ac", "bc", "abc" }

Constraints

|S| <= 10000

Input

First line of the input is number t (t <= 10000) denoting number of test cases. t lines follows, each containing string S, length of each string is at max 10000 (10^4).

Output

Output t strings, solution to each test.

Example

Input:
2
bcd
abcdefghijklmnnjoprstuvjklmqyz

Output:
a
aa