You are given string S. Find lexicographically smallest string, that is not a 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⁴).

Output

Output t strings, solution to each test.

Example

Input:
2
bcd
abcdefghijklmnnjoprstuvjklmqyz

Output:
a
aa