You are given a string $s$, consisting of lowercase Latin letters. While there is at least one character in the string $s$ that is repeated at least twice, you perform the following operation:

you choose the index $i$ ($1 \le i \le |s|$) such that the character at position $i$ occurs at least two times in the string $s$, and delete the character at position $i$, that is, replace $s$ with $s_1 s_2 \ldots s_{i-1} s_{i+1} s_{i+2} \ldots s_n$.

For example, if $s=$"codeforces", then you can apply the following sequence of operations:

$i=6 \Rightarrow s=$"codefrces";

$i=1 \Rightarrow s=$"odefrces";

$i=7 \Rightarrow s=$"odefrcs";

Given a given string $s$, find the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.

A string $a$ of length $n$ is lexicographically less than a string $b$ of length $m$, if:

there is an index $i$ ($1 \le i \le \min(n, m)$) such that the first $i-1$ characters of the strings $a$ and $b$ are the same, and the $i$-th character of the string $a$ is less than $i$-th character of string $b$;

or the first $\min(n, m)$ characters in the strings $a$ and $b$ are the same and $n < m$.

For example, the string $a=$"aezakmi" is lexicographically less than the string $b=$"aezus".


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

Each test case is characterized by a string $s$, consisting of lowercase Latin letters ($1 \le |s| \le 2 \cdot 10^5$).

It is guaranteed that the sum of the lengths of the strings in all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output the lexicographically maximum string that can be obtained after applying a certain sequence of operations after which all characters in the string become unique.


-----Examples-----

Input
6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz
Output
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Greedy algorithms

Complete search

Dynamic programming

Data structures


Solutions:
from queue import PriorityQueue
cas = int(input())
while cas:
	cas -= 1
	a = input()
	cnt = [0 for i in range(26)]
	vis = [0 for i in range(26)]
	for i in range(len(a)):
		c = ord(a[i]) - ord('a')
		cnt[c] += 1
	st = [30]
	s = 0
	for i in range(len(a)):
		tmp = ord(a[i]) - ord('a')
		if vis[tmp] == 0:
			while s and st[s] < tmp and (cnt[st[s]] >= 1):
				vis[st[s]] = 0
				st.pop(s)
				s -= 1
			st.append(tmp)
			s += 1
			vis[tmp] = 1
		cnt[tmp] -= 1
	for i in range(1, len(st)):
		c = chr(ord('a') + st[i])
		if i == len(st) - 1:
			print(c)
		else:
			print(c, end='')


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	s = [ord(i) - 97 for i in S()]
	n = len(s)
	v = [0] * 26
	used = [0] * 26
	for i in s:
		v[i] += 1
	ans = []
	ln = 0
	for i in range(n):
		v[s[i]] -= 1
		if used[s[i]]:
			continue
		used[s[i]] = 1
		ln += 1
		j = ln - 2
		while j >= 0 and ans[j] < s[i] and v[ans[j]]:
			used[ans.pop()] -= 1
			ln -= 1
			j -= 1
		ans += (s[i],)
	print(*[chr(i + 97) for i in ans], sep='')


import sys
input = sys.stdin.readline

def maxthestring3():
	for _ in range(int(input())):
		s = input().rstrip()
		lastpos = {v: i for (i, v) in enumerate(s)}
		queue = []
		his = set()
		for i in range(len(s)):
			nowl = s[i]
			if nowl not in his:
				if queue:
					while queue[-1] < nowl and lastpos[queue[-1]] > i:
						his.discard(queue.pop())
						if not queue:
							break
					queue.append(nowl)
					his.add(nowl)
				else:
					queue.append(nowl)
					his.add(nowl)
		print(''.join(queue))
maxthestring3()


from collections import Counter
for _ in range(int(input())):
	s = input()
	f = Counter(s)
	st = []
	onst = set()
	for (i, c) in enumerate(s):
		f[c] -= 1
		if c in onst:
			continue
		while st and c > st[-1] and f[st[-1]]:
			onst.remove(st.pop())
		st.append(c)
		onst.add(c)
	print(''.join(st))


for i in range(int(input())):
	s = input()
	if len(set(s[0:])) != len(s):
		while s:
			DEL = ''
			S = set(s[0:])
			abc = sorted(set(s[0:]))
			for j in range(len(abc) - 1, -1, -1):
				if len(set(s[s.index(abc[j]):])) == len(S):
					DEL = abc[j]
					break
			print(DEL, end='')
			s = s[s.index(DEL) + 1:]
			s = s.replace(DEL, '')
		print()
	else:
		print(s)


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_left
import heapq

def main():
	s = input()
	arr = list(set(s))
	arr.sort()
	n = len(arr)
	d = dict()
	for i in range(n):
		d[arr[i]] = i
	done = [0] * n
	ans = ''
	pt = 0
	for i in range(n):
		for j in range(n - 1, -1, -1):
			if not done[j]:
				idx = s.index(arr[j], pt)
				stt = set(s[idx:])
				sm = 0
				for ch in stt:
					if done[d[ch]] == 0:
						sm += 1
				if sm == n - sum(done):
					done[j] = 1
					pt = idx + 1
					ans += arr[j]
					break
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	ans = ''
	s = input()
	occ = {}
	for c in s:
		if c not in occ:
			occ[c] = 0
		occ[c] += 1
	remove = set()
	prev_i = -1
	for i in range(len(s)):
		occ[s[i]] -= 1
		if s[i] in remove:
			continue
		if prev_i == -1 or s[i] > s[prev_i]:
			prev_i = i
		if occ[s[i]] == 0:
			order = sorted(set(s[prev_i:i]), reverse=True)
			order_i = 0
			for j in range(prev_i, i):
				while order_i < len(order) and order[order_i] in remove:
					order_i += 1
				if order_i < len(order) and order[order_i] == s[j] and (s[j] >= s[i]) and (s[j] not in remove):
					ans += s[j]
					remove.add(s[j])
					prev_i = j
					order = sorted(set(s[prev_i:i]), reverse=True)
					order_i = 0
			if s[i] not in remove:
				ans += s[i]
				remove.add(s[i])
				prev_i = i
	print(ans)


import sys
input = sys.stdin.readline
from bisect import bisect
for _ in range(int(input())):
	s = input().strip()
	used = [0] * 26
	locs = [[] for i in range(26)]
	final_len = 26
	f = ''
	for i in range(len(s)):
		locs[ord(s[i]) - ord('a')].append(i)
	for i in range(26):
		if len(locs[i]) == 0:
			used[i] = 1
			final_len -= 1
	lst = -1
	for i in range(final_len):
		for j in range(25, -1, -1):
			if not used[j]:
				earliest = locs[j][bisect(locs[j], lst)]
				mn_latest = earliest
				for k in range(26):
					if not used[k]:
						mn_latest = min(mn_latest, locs[k][-1])
				if earliest <= mn_latest:
					used[j] = 1
					f += chr(ord('a') + j)
					lst = earliest
					break
	print(f)


import sys
max_int = 2147483648
min_int = -max_int
t = int(input())
for _t in range(t):
	s = input()
	d = {}
	for ss in s:
		if ss in d:
			d[ss] += 1
		else:
			d[ss] = 1
	st = []
	was = set()
	for ss in s:
		if ss not in was:
			while st and ss >= st[-1] and d[st[-1]]:
				was.discard(st[-1])
				st.pop()
			st.append(ss)
			was.add(ss)
		d[ss] -= 1
	print(''.join(st))


def charToInt(c):
	return ord(c) - ord('a')

def intToChar(x):
	return chr(ord('a') + x)

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		s = input()
		n = len(s)
		arr = [charToInt(c) for c in s]
		charIndexes = [[] for _ in range(26)]
		for (i, x) in enumerate(arr):
			charIndexes[x].append(i)
		availCharsAfter = [0 for _ in range(n)]
		for i in range(n - 1, -1, -1):
			b = 1 << arr[i]
			if i + 1 < n:
				availCharsAfter[i] = availCharsAfter[i + 1] | b
			else:
				availCharsAfter[i] = b
		requiredChars = set(arr)
		reqCharsBin = 0
		for x in requiredChars:
			reqCharsBin |= 1 << x
		ans = []
		currI = 0
		for __ in range(26):
			for char in range(25, -1, -1):
				if reqCharsBin & 1 << char == 0:
					continue
				tempArr = charIndexes[char]
				idx = -1
				bb = len(tempArr)
				while bb > 0:
					while idx + bb < len(tempArr) and tempArr[idx + bb] < currI:
						idx += bb
					bb //= 2
				nextI = tempArr[idx + 1]
				if reqCharsBin == reqCharsBin & availCharsAfter[nextI]:
					ans.append(intToChar(char))
					reqCharsBin = reqCharsBin & ~(1 << char)
					currI = nextI
					break
		allans.append(''.join(ans))
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _aa in range(1):
	main()


def count(s, remove=None):
	c = dict()
	y = ''
	o = ''
	for x in s:
		if x == y or x == remove:
			continue
		if x not in c:
			c[x] = 0
		c[x] += 1
		o += x
		y = x
	return (o, c)

def one(s):
	ptr = 0
	best = ''
	(s, c) = count(s)
	while True:
		leader = ''
		i = 0
		while i < len(s):
			x = s[i]
			if x in best:
				i += 1
				continue
			c[x] -= 1
			if x > leader:
				leader = x
				li = i
			if c[x] == 0:
				break
			i += 1
		best += leader
		ptr = li + 1
		if ptr > len(s):
			break
		(s, c) = count(s[li + 1:], leader)
	return best
for _ in range(int(input())):
	s = input()
	r = one(s)
	print(f'{r}')


for nt in range(int(input())):
	s = input()
	n = len(s)
	vis = [0] * 26
	d = {}
	for i in range(n):
		d[s[i]] = i
	ans = []
	stack = []
	for i in range(n):
		if not vis[ord(s[i]) - 97]:
			while stack and s[i] > stack[-1] and (i < d[stack[-1]]):
				vis[ord(stack.pop()) - 97] = 0
			stack.append(s[i])
			vis[ord(s[i]) - 97] = 1
	print(''.join(stack))


for i in range(int(input())):
	s = input()
	if len(set(s[0:])) != len(s):
		n = len(set(s[0:]))
		a = sorted(set(s[0:]))
		while s:
			DEL = ''
			for j in range(len(a) - 1, -1, -1):
				if len(set(s[s.index(a[j]):])) == n:
					DEL = a[j]
					break
			print(DEL, end='')
			s = s[s.index(DEL) + 1:]
			s = s.replace(DEL, '')
			n -= 1
			a.pop(a.index(DEL))
		print()
	else:
		print(s)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	s = input()
	n = len(s)
	vis = AI(26, 1)
	res = [deque() for i in range(26)]
	for (i, ch) in enumerate(s):
		res[ord(ch) - 97].append(i)
		vis[ord(ch) - 97] = 0
	ans = []
	for i in range(26):
		for j in range(25, -1, -1):
			f = True
			if not vis[j]:
				for k in range(j - 1, -1, -1):
					if not vis[k] and res[k][-1] < res[j][0]:
						f = False
						break
				if f:
					vis[j] = 1
					ans.append(chr(j + 97))
					cur = res[j][0]
					res[j] = []
					for i in range(26):
						while res[i] and res[i][0] < cur:
							res[i].popleft()
					break
	ans = ''.join(ans)
	print(ans)


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for tests in range(t):
	S = input().strip()
	X = [deque() for i in range(26)]
	for i in range(len(S)):
		X[ord(S[i]) - 97].append(i)
	LEN = 0
	for i in range(26):
		if len(X[i]) > 0:
			LEN += 1
	ANS = [-1] * LEN
	for i in range(LEN):
		for j in range(25, -1, -1):
			if len(X[j]) == 0:
				continue
			tu = X[j][0]
			for k in range(j - 1, -1, -1):
				if len(X[k]) == 0 or X[k][-1] > tu:
					continue
				else:
					break
			else:
				ANS[i] = chr(j + 97)
				X[j] = []
				break
		for j in range(25):
			while len(X[j]) > 0 and X[j][0] <= tu:
				X[j].popleft()
	print(''.join(ANS))


for _ in range(int(input())):
	s = input()
	l = len(s)
	stack = []
	d = {i: v for (v, i) in enumerate(s)}
	st = set()
	for i in range(l):
		if s[i] not in st:
			while stack and s[i] > stack[-1] and (d[stack[-1]] > i):
				st.discard(stack.pop())
			stack.append(s[i])
			st.add(s[i])
	print(''.join(stack))


from sys import stdin, stdout
import heapq
from collections import defaultdict
import math
import bisect

def main():
	t = int(stdin.readline())
	for _ in range(t):
		s = stdin.readline().strip()
		alp = [0 for _ in range(27)]
		for (i, x) in enumerate(s):
			alp[ord(x) - 97] += 1
		ans = []
		for (i, x) in enumerate(s):
			if not ans:
				ans.append(x)
				continue
			if x in ans:
				alp[ord(x) - 97] -= 1
				continue
			while ans and x >= ans[-1] and (alp[ord(ans[-1]) - 97] > 1):
				alp[ord(ans[-1]) - 97] -= 1
				ans.pop()
			ans.append(x)
		stdout.write(''.join(ans) + '\n')
main()


try:
	import collections
	from heapq import *
	test = int(input())
	while test != 0:
		inp = input()
		string = list(inp)
		n = len(string)
		cnt = collections.defaultdict(int)
		for a in string:
			cnt[a] += 1
		ans = []
		heap = []
		pj = -1
		for (i, a) in enumerate(string):
			if cnt[a]:
				heappush(heap, (-ord(a), i))
				cnt[a] -= 1
				if cnt[a] == 0:
					while heap:
						(b, j) = heappop(heap)
						b = chr(-b)
						if b == a and j > pj:
							ans.append(b)
							pj = j
							break
						if j > pj and cnt[b]:
							ans.append(b)
							cnt[b] = 0
							pj = j
		print(''.join(ans))
		test -= 1
except EOFError as e:
	print(' ')


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
for _ in range(val()):
	s = st()
	stack = []
	last = {}
	for i in range(len(s)):
		last[s[i]] = i
	n = len(set(s))
	ans = ''
	for i in range(len(s)):
		add = 1
		if s[i] in ''.join((s[k] for k in stack)):
			continue
		for j in list(stack)[::-1]:
			if s[j] > s[i]:
				continue
			elif s[j] < s[i]:
				if last[s[j]] < i:
					if s[i] in ''.join((s[k] for k in stack)):
						add = 0
					break
				else:
					stack.remove(j)
			else:
				stack.remove(j)
		if add:
			stack.append(i)
	ans = ''.join((s[j] for j in stack))
	print(ans)


t = int(input())
for j in range(t):
	s = input()
	n = len(s)
	d = {}
	for i in range(n):
		d[s[i]] = i
	ans = []
	st = set()
	for i in range(n):
		if s[i] not in st:
			while ans and s[i] > ans[-1] and (d[ans[-1]] > i):
				st.remove(ans.pop())
			ans.append(s[i])
			st.add(s[i])
	print(*ans, sep='')


from collections import deque
from string import ascii_lowercase

def can_be_deleted(s, i, letters):
	return s[i] != '$' and letters[ord(s[i]) - ord('a')][-1] > i

def add_q(q, s, j, i):
	while q and q[0] < i:
		q.pop()
	while q and s[q[-1]] <= s[j]:
		q.pop()
	q.append(j)

def ch2int(ch):
	return ord(ch) - ord('a')

def getIndex(new_ch, rem, start, letters):
	chars = set(t)
	closest = letters[ch2int(new_ch)][start]
	if closest == -1:
		return -1
	for ch in rem:
		if ch != new_ch:
			if letters[ch2int(ch)][closest + 1] == -1:
				return -1
	return closest
for _ in range(int(input())):
	s = input()
	t = []
	letters = [[-1] * (len(s) + 1) for _ in range(26)]
	i = len(s) - 1
	while i >= 0:
		for j in range(26):
			if j == ch2int(s[i]):
				letters[j][i] = i
			else:
				letters[j][i] = letters[j][i + 1]
		i -= 1
	rem = sorted(set(s), reverse=True)
	start = 0
	for _ in range(len(rem)):
		for ch in rem:
			idx = getIndex(ch, rem, start, letters)
			if idx != -1:
				start = idx + 1
				rem.remove(ch)
				t.append(ch)
				break
	print(''.join(t))


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict, Counter

def main():
	for _ in range(int(input())):
		s = input().rstrip()
		(n, d) = (len(s), set(s))
		(ans, l, indd) = ([], len(d), 0)
		while len(ans) < l:
			(z, a) = (0, set())
			for i in range(n - 1, indd - 1, -1):
				if s[i] not in a and s[i] in d:
					z += 1
					a.add(s[i])
				if z == len(d):
					ma = ''
					for j in range(indd, i + 1, 1):
						if s[j] in d and ma < s[j]:
							ma = s[j]
							ind = j
					ans.append(ma)
					indd = ind
					d.discard(ma)
					break
		print(''.join(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import deque, Counter
for idx in range(int(input())):
	s = input()
	count = Counter(s)
	check = {i: 0 for i in count.keys()}
	stack = []
	for i in range(len(s)):
		count[s[i]] -= 1
		if check[s[i]]:
			continue
		while len(stack) and s[i] > stack[-1] and count[stack[-1]]:
			x = stack.pop()
			check[x] = 0
		stack.append(s[i])
		check[s[i]] = 1
	print(''.join(stack))


from collections import Counter

def get_input():
	l = [int(e) for e in input().split()]
	return l

def possible_char(i, c, s):
	n = len(s)
	possiblities = set()
	ctemp = c.copy()
	while i < n and ctemp[s[i]] != 1:
		if ctemp[s[i]] > 0:
			possiblities.add(s[i])
			ctemp[s[i]] -= 1
		i += 1
	if i < n:
		possiblities.add(s[i])
	return possiblities

def main(s):
	sol = []
	n = len(s)
	i = 0
	c = Counter(s)
	while i < n:
		possiblities = possible_char(i, c, s)
		if len(possiblities) == 0:
			break
		nc = max(possiblities)
		sol.append(nc)
		while i < n and s[i] != nc:
			c[s[i]] -= 1
			i += 1
		c[nc] = 0
		i += 1
	print(''.join(sol))
t = get_input()[0]
for _ in range(t):
	s = input()
	main(s)


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase
from collections import Counter

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	for _ in range(int(input())):
		s = input().strip()
		n = len(s)
		ans = []
		cou = Counter(s)
		se = [0] * 26
		yy = SortedList()
		ls = 0
		for i in range(n):
			cou[s[i]] -= 1
			zz = ord(s[i]) - 97
			if not se[zz]:
				yy.add(zz)
				if not cou[s[i]]:
					for j in range(ls, i + 1):
						z = ord(s[j]) - 97
						if len(yy) and z == yy[-1] and (not se[z]):
							ans.append(s[j])
							se[z] = 1
							while z in yy:
								yy.remove(z)
							if s[j] == s[i]:
								break
						yy.discard(z)
					ls = j + 1
		print(''.join(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


import io
import os

def solve():
	s = input()
	s = [-1] + list([ord(c) - ord('a') for c in s])
	n = len(s)
	next = [[n] * n for _ in range(26)]
	for i in range(n - 2, -1, -1):
		for c in range(26):
			next[c][i] = next[c][i + 1]
			if s[i + 1] == c:
				next[c][i] = i + 1
	ans = []
	pos = 0
	rem = set(s[1:])
	while rem:
		for c in sorted(rem, reverse=True):
			if not any((next[oc][next[c][pos]] == n for oc in rem - {c})):
				pos = next[c][pos]
				ans.append(c)
				rem.remove(c)
				break
	print(''.join((chr(ord('a') + c) for c in ans)))
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	S = list(map(lambda x: ord(x) - ord('a'), list(input())[:-1]))
	n = len(S)
	table = [0] * 26
	res = []
	for x in S:
		table[x] += 1
	last = 0
	for _ in range(len(set(S))):
		c = 0
		start = last
		for i in range(last, n):
			x = S[i]
			if table[x] > 1:
				if c < x:
					c = x
					last = i + 1
				table[x] -= 1
			elif table[x] == 1:
				if c < x:
					c = x
					last = i + 1
				table[x] -= 1
				break
		res.append(c)
		for j in range(last, i + 1):
			table[S[j]] += 1
		for x in res:
			table[x] = 0
	print(''.join([chr(x + ord('a')) for x in res]))


t = int(input())
for _ in range(t):
	S = input()
	l = [[] for i in range(26)]
	for i in range(len(S)):
		l[ord(S[i]) - ord('a')].append(i)
	last = [10 ** 10] * 26
	for i in range(26):
		if l[i]:
			l[i] = l[i][::-1]
			last[i] = l[i][0]
	ans = ''
	now = -1
	while True:
		nex = 10 ** 10
		ind = -1
		for i in range(26):
			if nex > last[i]:
				nex = last[i]
				ind = i
			nex = min(nex, last[i])
		if ind == -1:
			break
		for i in range(26)[::-1]:
			if last[i] == 10 ** 10:
				continue
			while l[i] and l[i][-1] <= now:
				l[i].pop()
			if l[i] and l[i][-1] <= nex:
				ans += chr(ord('a') + i)
				now = l[i][-1]
				last[i] = 10 ** 10
				break
	print(ans)


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input().strip()
	n = len(s)
	d = {}
	for i in s:
		d[i] = d.get(i, 0) + 1
	l = len(d)
	used = set()
	places = []
	last = 0
	for p in range(l):
		for j in range(25, -1, -1):
			if j in used:
				continue
			f = 0
			for i in range(last, n):
				if ord(s[i]) - 97 == j:
					used.add(j)
					places.append(s[i])
					last = i + 1
					f = 1
					for k in range(last, i):
						d[s[k]] += 1
					break
				else:
					d[s[i]] -= 1
					if d[s[i]] == 0:
						for k in range(last, i + 1):
							d[s[k]] += 1
						break
			if f:
				break
	print(''.join(places))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
from collections import deque
for _ in range(int(input()) if True else 1):
	s = [ord(c) - 97 for c in input()]
	last = [-1] * 26
	first = [deque() for i in range(26)]
	lasts = []
	for i in range(len(s) - 1, -1, -1):
		if last[s[i]] == -1:
			last[s[i]] = i
			lasts += [i]
	for i in range(len(s)):
		first[s[i]] += [i]
	ans = []
	used = set()
	cur = 0
	while lasts:
		mx = min(lasts)
		for i in range(25, -1, -1):
			if not first[i] or i in used:
				continue
			if first[i][0] <= mx:
				ans.append(chr(97 + i))
				used.add(i)
				lasts.remove(last[i])
				c2 = first[i][0] + 1
				for j in range(cur, first[i][0] + 1):
					first[s[j]].popleft()
				cur = c2
				break
	print(*ans, sep='')


import sys
for _ in range(int(input())):
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	v = [False for i in range(26)]
	temp = []
	for i in s:
		d[i] -= 1
		if v[ord(i) - ord('a')] == True:
			continue
		while temp and temp[-1] < i and (d[temp[-1]] > 0):
			now = temp.pop()
			v[ord(now) - ord('a')] = False
		v[ord(i) - ord('a')] = True
		temp.append(i)
	ans = ''
	for i in temp:
		ans += i
	print(ans)


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
t = ri()
for _ in range(t):
	s = rl()
	n = len(s)
	last = {c: i for (i, c) in enum(s)}
	last[''] = -1
	used = {''}
	stk = ['']
	for (i, c) in enum(s):
		if c in used:
			continue
		while stk[-1] < c and i < last[stk[-1]]:
			used.discard(stk.pop())
		stk.append(c)
		used.add(c)
	ans = ''.join(stk)
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = 0
	while left <= right:
		mid = (right + left) // 2
		if arr[mid][0] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
for i in range(int(input())):
	s = input()
	n = len(s)
	res = []
	used = set()
	last = {c: i for (i, c) in enumerate(s)}
	for i in range(n):
		if s[i] not in used:
			while res and res[-1] < s[i] and (i < last[res[-1]]):
				used.remove(res.pop())
			res.append(s[i])
			used.add(s[i])
	print(''.join(res))


import sys
import collections
from copy import copy, deepcopy
from typing import OrderedDict

class Solution:

	def trim(self):
		return input()

	def rInt(self):
		return int(self.trim())

	def rStr(self):
		return str(self.trim())

	def rCharList(self):
		s = self.trim()
		return list(s[:len(s) - 1])

	def rIntMap(self):
		return map(int, self.trim().split())

	def rIntList(self):
		return list(self.rIntMap())

	def rStrList(self):
		return list(map(str, self.trim().split()))

	def process(self, case, S):
		(s, visited) = ([], set())
		n = len(S)
		last = {v: i for (i, v) in enumerate(S)}
		left = 1
		for i in range(n):
			if S[i] not in visited:
				while s and i < last[s[-1]] and (s[-1] < S[i]):
					visited.discard(s.pop())
				if left:
					s.append(S[i])
				left += 1
				visited.add(S[i])
		print(''.join(s))

def main():
	s = Solution()
	tc = s.rInt()
	for i in range(tc):
		S = s.rStr()
		s.process(i + 1, S)
main()


from sys import stdin

def solve(tc):
	s = stdin.readline().strip()
	n = len(s)
	si = [0 for i in range(n)]
	remaining = [0 for i in range(26)]
	for i in range(n):
		key = ord(s[i]) - ord('a')
		si[i] = key
		remaining[key] += 1
	st = []
	curUsed = [0 for i in range(26)]
	for i in range(n):
		if curUsed[si[i]] > 0:
			remaining[si[i]] -= 1
			continue
		while len(st) > 0 and st[-1] < si[i] and (remaining[st[-1]] > 0):
			pick = st.pop()
			curUsed[pick] -= 1
		st.append(si[i])
		curUsed[si[i]] += 1
		remaining[si[i]] -= 1
	print(*list(map(lambda x: chr(x + ord('a')), st)), sep='')
tcs = 1
tcs = int(stdin.readline().strip())
tc = 1
while tc <= tcs:
	solve(tc)
	tc += 1


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve(s):
	n = len(s)
	c = [0] * 27
	c[0] = 1
	for i in s:
		c[i - 96] += 1
	(q, r) = ([123], [])
	for i in range(n + 1):
		if i < n:
			ch = s[i]
		else:
			ch = 96
		if c[ch - 96] == 1:
			nq = [123]
			f = 0
			for j in q[1:]:
				if j > ch:
					r.append(j)
					c[j - 96] = 0
				elif j == ch:
					f = 1
				elif f:
					nq.append(j)
			r.append(ch)
			q = nq
		elif c[ch - 96] > 1:
			if ch not in q:
				while q[-1] <= ch:
					q.pop()
				q.append(ch)
			c[ch - 96] -= 1
	return ''.join(map(chr, r[:-1]))
O = []
for _ in range(int(input())):
	s = input().strip()
	O.append(solve(s))
print('\n'.join(O))


import copy, math, random, re, sys, time

def input_int():
	return int(input())

def input_int_list():
	return list(map(int, input().split()))

def input_str():
	return input()

def input_str_list():
	return input().split()
t = input_int()
for idx in range(1, t + 1):
	s = input_str()
	i = 0
	while i < len(s):
		letter_count = {}
		for l in s[i:]:
			letter_count[l] = letter_count[l] + 1 if l in letter_count else 1
		max_letter = ''
		max_letter_idx = -1
		for j in range(i, len(s)):
			if max_letter == '' or ord(s[j]) > ord(max_letter):
				max_letter = s[j]
				max_letter_idx = j
			letter_count[s[j]] = letter_count[s[j]] - 1
			if letter_count[s[j]] == 0:
				break
		prefix = s[:i]
		new_letter = s[max_letter_idx]
		suffix = s[max_letter_idx + 1:].replace(s[max_letter_idx], '')
		s = prefix + new_letter + suffix
		i += 1
	print(s)


for _ in range(int(input())):
	s = input()
	stack = []
	seen = set()
	last_occurrence = {c: i for (i, c) in enumerate(s)}
	for (i, c) in enumerate(s):
		if c not in seen:
			while stack and c > stack[-1] and (i < last_occurrence[stack[-1]]):
				seen.discard(stack.pop())
			seen.add(c)
			stack.append(c)
	print(''.join(stack))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
import heapq as h, time
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	S = listStr()
	N = len(S)
	indices = [[] for _ in range(26)]
	orda = ord('a')
	assigned = [N]
	to_use = set()
	for (i, s) in enumerate(S):
		indices[ord(s) - orda].append(i)
		to_use.add(ord(s) - orda)
	ans = []
	to_use = sorted(list(to_use))
	for i in range(26):
		indices[i].reverse()
	while to_use:
		flag = True
		idx = len(to_use) - 1
		while flag:
			j = to_use[idx]
			flag = False
			for x in to_use[:-1]:
				if indices[x][0] < indices[j][-1]:
					flag = True
					break
			idx -= 1
		idx += 1
		ans.append(j)
		to_use.pop(idx)
		idx = indices[j][-1]
		for x in to_use:
			while indices[x] and indices[x][-1] < idx:
				indices[x].pop()
	ans = [chr(orda + a) for a in ans]
	return ''.join(ans)
for _ in range(getInt()):
	print(solve())


from collections import Counter
n = int(input())
for i in range(n):
	s = input()
	f = Counter(s)
	stack = []
	seen = set()
	for i in s:
		f[i] -= 1
		if i in stack:
			continue
		while stack and stack[-1] < i and (f[stack[-1]] != 0):
			stack.pop()
		stack.append(i)
		seen.add(i)
	print(''.join(stack))


from typing import Set, Deque, Dict, List, Tuple, Any, OrderedDict, DefaultDict
import math
from functools import total_ordering
from queue import deque, PriorityQueue
from collections import OrderedDict as Map

@total_ordering
class MyComparer(object):

	def __init__(self, first, second):
		self.first = first
		self.second = second

	def __lt__(self, other):
		if self.first == other.first:
			return self.second > other.second
		return self.first > other.first

class Problem(object):

	def removeDuplicateLetters(self, s):
		cnt = [0] * 26
		vis = [0] * 26
		n = len(s)
		for i in s:
			cnt[ord(i) - ord('a')] += 1
		res = []
		for i in range(n):
			cnt[ord(s[i]) - ord('a')] -= 1
			if not vis[ord(s[i]) - ord('a')]:
				while len(res) > 0 and res[-1] < s[i] and (cnt[ord(res[-1]) - ord('a')] > 0):
					vis[ord(res[-1]) - ord('a')] = 0
					del res[-1]
				res += s[i]
				vis[ord(s[i]) - ord('a')] = 1
		return ''.join(res)

	def solve(self):
		s = input()
		out = self.removeDuplicateLetters(s)
		print(out)
tc = 1
tc = int(input())
for _ in range(tc):
	problem = Problem()
	problem.solve()


n = int(input())
for _ in range(n):
	s = input()
	n = len(s)
	ch_set = set(s)
	t = ''
	for i in range(len(ch_set)):
		for ch in sorted(ch_set, reverse=True):
			if set(s[s.find(ch):]).issuperset(ch_set):
				s = s[s.find(ch):].replace(ch, '')
				ch_set.remove(ch)
				t += ch
				break
	print(t)


t = int(input())
for _ in range(t):
	list_s = input()
	lastPositions = {c: pos for (pos, c) in enumerate(list_s)}
	assigned = {c: False for c in lastPositions}
	new_string = []
	for (pos, c) in enumerate(list_s):
		if len(new_string) == len(assigned):
			break
		if not assigned[c]:
			i = len(new_string) - 1
			while i >= 0 and new_string[i] < c and (pos < lastPositions[new_string[i]]):
				assigned[new_string[i]] = False
				i -= 1
			new_string = new_string[:i + 1]
			new_string.append(c)
			assigned[c] = True
	print(''.join(new_string))


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(ii()):
		s = si()
		n = len(s)
		vis = [1] * 26
		store = [[] for i in range(26)]
		for i in range(n):
			c = bo(s[i])
			vis[c] = 0
			store[c].append(i)
		l = 0
		op = 0
		ans = ''
		while l < n and op < 26:
			op += 1
			for i in range(25, -1, -1):
				if vis[i]:
					continue
				idx = bisect_left(store[i], l)
				if idx >= len(store[i]):
					continue
				pos = store[i][idx]
				f = 0
				for j in range(26):
					if j == i or vis[j]:
						continue
					if store[j][-1] < pos:
						f = 1
						break
				if f == 0:
					vis[i] = 1
					l = pos + 1
					ans += chr(97 + i)
					break
		print(ans)
if file:
	if path.exists('tmp/input.txt'):
		sys.stdin = open('tmp/input.txt', 'r')
		sys.stdout = open('tmp/output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


t = int(input())
from collections import Counter
for i in range(t):
	s = input()
	n = len(s)
	res = []
	used = set()
	last = {c: i for (i, c) in enumerate(s)}
	for i in range(n):
		if s[i] not in used:
			while res and res[-1] < s[i] and (i < last[res[-1]]):
				used.remove(res.pop())
			res.append(s[i])
			used.add(s[i])
	print(''.join(res))


import sys
input = sys.stdin.readline
t = int(input().strip())
for __ in range(t):
	s = input().strip()
	cnt = [0] * 26
	vis = [0] * 26
	n = len(s)
	for i in s:
		cnt[ord(i) - ord('a')] += 1
	res = []
	for (i, c) in enumerate(s):
		cnt[ord(c) - ord('a')] -= 1
		if not vis[ord(c) - ord('a')]:
			while len(res) > 0 and res[-1] < c and (cnt[ord(res[-1]) - ord('a')] > 0):
				vis[ord(res[-1]) - ord('a')] = 0
				del res[-1]
			res += [c]
			vis[ord(c) - ord('a')] = 1
	print(''.join(res))


import sys
import math
from itertools import permutations
from bisect import bisect_left
import heapq
from collections import deque

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	s = list(SI())
	for i in range(len(s)):
		s[i] = ord(s[i]) - 97
	d = [0 for i in range(26)]
	dd = [0 for i in range(26)]
	count = 0
	need = []
	for i in range(len(s)):
		dd[s[i]] = i
		d[s[i]] += 1
		if d[s[i]] == 1:
			count += 1
			need.append(s[i])
	ans = [0 for i in range(count)]
	ind = 0
	for i in range(count):
		m = -1
		ii = -1
		for j in range(ind, len(s)):
			boo = True
			for k in need:
				if j > dd[k]:
					boo = False
					break
			if not boo:
				break
			if s[j] in need and s[j] > m:
				m = s[j]
				ii = j
		ans[i] = m
		ind = ii + 1
		need.remove(m)
	for i in range(count):
		ans[i] = chr(ans[i] + 97)
	print(''.join(ans))


from collections import Counter

def solve(S):
	cs = Counter(S)
	stack = []
	vis = set()
	for i in range(len(S)):
		if S[i] not in vis:
			while stack and stack[-1] < S[i] and (cs[stack[-1]] > 0):
				vis.discard(stack.pop())
			vis.add(S[i])
			stack.append(S[i])
		cs[S[i]] -= 1
	return ''.join(stack)
T = int(input())
for _ in range(T):
	S = input()
	print(solve(S))


import math
import sys
from collections import Counter
from heapq import heappush, heappop
from typing import List
input = sys.stdin.readline

def inp():
	return int(input())

def instr():
	return str(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(map(int, list(s[:len(s) - 1])))

def invr():
	return map(int, input().split())

def main():
	t = inp()
	for _ in range(t):
		s = instr().strip()
		counter = Counter(s)
		results = {''}
		for (i, c) in enumerate(s):
			counter[c] -= 1
			new_res = set()
			for r in results:
				if c in r:
					new_res.add(r)
					continue
				else:
					new_res.add(r + c)
				if counter[c] > 0:
					new_res.add(r)
			results = new_res
			lens = set()
			new_res = set()
			for r in sorted(list(results), reverse=True):
				if len(r) not in lens:
					new_res.add(r)
					lens.add(len(r))
			results = new_res
		print(sorted(list(results), reverse=True)[0])
main()


t = int(input())
for _ in range(t):
	s = str(input())
	n = len(s)
	dict1 = {}
	for i in range(n):
		dict1[ord(s[i])] = i
	stack = []
	vis = [0] * 26
	for i in range(n):
		if vis[ord(s[i]) - 97] == 0:
			while stack and ord(s[i]) > stack[-1] and (i < dict1[stack[-1]]):
				vis[stack.pop() - 97] = 0
			stack.append(ord(s[i]))
			vis[ord(s[i]) - 97] = 1
	for i in stack:
		print(chr(i), end='')
	print('')


import sys
from collections import defaultdict
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	ind = [[] for i in range(26)]
	val = [1] * n
	for j in range(n):
		ind[ord(s[j]) - 97].append(j)
	ans = []
	j = 0
	vis = defaultdict(lambda : 0)
	while j < n - 1:
		curr = j + 1
		if not vis[s[j]]:
			while curr < n:
				if s[j] >= s[curr]:
					if not vis[s[curr]] and ind[ord(s[curr]) - 97][-1] == curr:
						break
				elif not vis[s[curr]]:
					break
				curr += 1
			if curr == n:
				ans.append(s[j])
				vis[s[j]] = 1
				j += 1
			elif s[j] > s[curr]:
				ans.append(s[j])
				vis[s[j]] = 1
				j += 1
			elif s[j] == s[curr]:
				ans.append(s[j])
				vis[s[j]] = 1
				j += 1
			elif ind[ord(s[j]) - 97][-1] > curr:
				j = curr
			else:
				ans.append(s[j])
				vis[s[j]] = 1
				j = curr
		else:
			j += 1
	if not vis[s[-1]]:
		ans.append(s[-1])
	print(''.join(ans))


from collections import deque, defaultdict

def def_value():
	return 0

def func(s):
	stack = deque()
	hashmap = defaultdict(def_value)
	count = defaultdict(def_value)
	for i in s:
		count[i] += 1
	for i in range(len(s)):
		if not hashmap[s[i]]:
			while len(stack) and s[i] > stack[-1] and (count[stack[-1]] >= 1):
				h = stack.pop()
				hashmap[h] = 0
		if hashmap[s[i]]:
			count[s[i]] -= 1
		else:
			stack.append(s[i])
			hashmap[s[i]] = 1
			count[s[i]] -= 1
	string = ''
	while stack:
		string += stack.pop()
	return string[::-1]
n = int(input())
for i in range(n):
	s = input()
	print(func(s))


import sys

def can(tc, s, A, chars):
	t = tc[:-1]
	c = tc[-1]
	j = 0
	for i in range(len(s)):
		if not t:
			break
		if s[i] == t[j]:
			j += 1
		if j == len(t):
			break
	i = i + 1 if t else 0
	found = False
	while i < len(s):
		if s[i] == c:
			found = True
			break
		i += 1
	i += 1
	if not found:
		return False
	if A[i] | set(list(t)) | {c} == set(chars):
		return True
	return False
prev = None
for _ in range(int(input())):
	s = input()
	if s == prev:
		print(t)
		continue
	A = [set() for _ in range(len(s) + 1)]
	for i in range(len(s) - 1, -1, -1):
		A[i] |= A[i + 1] | {s[i]}
	chars = list(set(list(s)))
	chars.sort(reverse=True)
	t = ''
	while len(t) < len(chars):
		for char in chars:
			if char not in t and can(t + char, s, A, chars):
				t += char
				break
	prev = s
	print(t)


import collections

def solve(s):
	if not s:
		return ''
	counts = collections.Counter(list(s))
	pos = 0
	for (i, x) in enumerate(s):
		if x > s[pos]:
			pos = i
		counts[x] -= 1
		if counts[x] == 0:
			break
	return s[pos] + solve(s[pos + 1:].replace(s[pos], ''))
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


import sys
input = sys.stdin.readline
from collections import *
for _ in range(int(input())):
	s = input()[:-1]
	n = len(s)
	idx = defaultdict(lambda : deque([]))
	acc = [[0] for _ in range(26)]
	for i in range(n):
		c = ord(s[i]) - ord('a')
		idx[c].append(i)
		for j in range(26):
			acc[j].append(acc[j][-1] + (1 if j == c else 0))
	flag = [False] * 26
	for i in range(26):
		if len(idx[i]) > 0:
			flag[i] = True
	m = flag.count(True)
	ans = []
	for _ in range(m):
		for i in range(25, -1, -1):
			if not flag[i]:
				continue
			ok = True
			for j in range(26):
				if flag[j] and j != i and (acc[j][n] - acc[j][idx[i][0]] == 0):
					ok = False
			if ok:
				ans.append(chr(i + ord('a')))
				flag[i] = False
				for j in range(26):
					while len(idx[j]) > 0 and idx[j][0] < idx[i][0]:
						idx[j].popleft()
				break
	print(''.join(ans))


def CountAparicions(s):
	repeatedChars = {}
	for i in range(len(s)):
		char = s[i]
		if char in repeatedChars:
			repeatedChars[char] += 1
		else:
			repeatedChars[char] = 1
	return repeatedChars

def MaxSubStr(word, NewWord=''):
	if word == '':
		return NewWord
	possibleLetters = []
	numberOfAparicions = {}
	counted = CountAparicions(word)
	for letter in word:
		if letter in possibleLetters:
			numberOfAparicions[letter] += 1
			if numberOfAparicions[letter] == counted[letter]:
				break
		else:
			numberOfAparicions[letter] = 1
		possibleLetters.append(letter)
		if counted[letter] == 1:
			break
	del numberOfAparicions
	NewLetter = max(possibleLetters)
	NewLetterIndex = word.find(NewLetter)
	word = word[NewLetterIndex + 1:]
	NewWord += NewLetter
	word = word.replace(NewLetter, '')
	return MaxSubStr(word, NewWord)
numberIterations = int(input())
i = 0
while i < numberIterations:
	s = input()
	s = ''.join((e for e in s if e.isalpha()))
	if s == '':
		continue
	s1 = MaxSubStr(s)
	print(s1)
	i += 1


from sys import stdin, stdout

def maximize_the_remaining_string(s):
	check_a = [False] * 26
	c_a = [[] for _ in range(26)]
	hs = set()
	for i in range(len(s)):
		c_a[ord(s[i]) - ord('a')].append(i)
		check_a[ord(s[i]) - ord('a')] = True
		hs.add(s[i])
	r = ''
	p = -1
	for _ in range(len(hs)):
		for i in range(25, -1, -1):
			if not check_a[i]:
				continue
			l = 0
			h = len(c_a[i])
			while l < h:
				m = (l + h) // 2
				if c_a[i][m] <= p:
					l = m + 1
				else:
					h = m
			found = True
			for j in range(i - 1, -1, -1):
				if not check_a[j]:
					continue
				if c_a[i][h] > c_a[j][-1]:
					found = False
					break
			if found:
				check_a[i] = False
				r += chr(i + ord('a'))
				p = c_a[i][h]
				break
	return r
t = int(stdin.readline())
for _ in range(t):
	s = stdin.readline().strip()
	r = maximize_the_remaining_string(s)
	stdout.write(str(r) + '\n')


for _ in range(int(input())):
	stroke = input()
	arr = {b: a for (a, b) in enumerate(stroke)}
	tec = []
	tecs = set()
	for (num, j) in enumerate(stroke):
		if j not in tecs:
			while len(tec) != 0 and tec[-1] < j and (num < arr[tec[-1]]):
				tecs.discard(tec.pop())
			tec.append(j)
			tecs.add(j)
	print(*tec, sep='')


t = int(input())
for k in range(t):
	a = input()
	b = list(a)
	new = []
	povt = {}
	for i in b:
		if i in povt.keys():
			povt[i] += 1
		else:
			povt[i] = 1
	i = 0
	while i < len(b) - 1:
		if b[i] in b[:i]:
			povt[b[i]] -= 1
			b.pop(i)
			if i < 0:
				i -= 1
		elif povt[b[i]] > 1:
			if b[i + 1] in b[:i + 1]:
				povt[b[i + 1]] -= 1
				b.pop(i + 1)
			elif ord(b[i + 1]) >= ord(b[i]):
				povt[b[i]] -= 1
				b.pop(i)
				if i > 0:
					i -= 1
				continue
			elif ord(b[i + 1]) < ord(b[i]):
				i += 1
		else:
			i += 1
	if povt[b[-1]] > 1:
		b.pop(-1)
	print(*b, sep='')


from sys import stdin, stdout

def input():
	return stdin.readline().strip()

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
from collections import defaultdict
from itertools import product
ALPHABET = 'abcdefghijklmnopqrstuvwxyz'[::-1]

def ans_slow(S):
	indexes = defaultdict(set)
	for (i, c) in enumerate(S):
		indexes[c].add(i)
	keys = []
	values = []
	for c in ALPHABET:
		if len(indexes[c]) > 0:
			keys += [c]
			values += [indexes[c]]
	candidates = []
	for ic in product(*values):
		candidate = sorted(list(zip(ic, keys)))
		candidate = [c for (_, c) in candidate]
		candidates += [''.join(candidate)]
	return max(candidates)

def ok(s1, s2):
	for c in set(s1):
		if c not in s2:
			return False
	return True

def ans(S):

	def index(S, i, c):
		for j in range(i, len(S)):
			if S[j] == c:
				return j
		return None
	assigned = []
	while len(S):
		for c in ALPHABET:
			if c in assigned:
				continue
			i = index(S, 0, c)
			if i is None:
				continue
			if ok(S[0:i], S[i + 1:]):
				assigned += [c]
				S = S[i:].replace(c, '')
				break
	assigned = ''.join(assigned)
	return assigned
if False:
	import sys, random
	for _ in range(10000):
		tc = ''.join((random.choice('abcde') for _ in range(10)))
		if ans(tc) != ans_slow(tc):
			print(tc, ans(tc), ans_slow(tc))
			sys.exit(0)
	sys.exit(0)
for _ in range(read_int()):
	S = input()
	print(ans(S))


import string
alph = string.ascii_lowercase

def main():
	t = int(input())
	for _ in range(t):
		s = input()
		n = len(s)
		d = {}
		s2 = ''
		for i in range(n):
			d[s[i]] = i
		cnt = 0
		begin = 0
		while cnt < len(d):
			Mx = -1
			for i in range(begin, n):
				if d[s[i]] == -1:
					continue
				if Mx == -1 or s[i] > s[Mx]:
					Mx = i
				if d[s[i]] == i:
					s2 += s[Mx]
					d[s[Mx]] = -1
					cnt += 1
					begin = Mx + 1
					break
		print(s2)
main()


from collections import Counter, defaultdict, OrderedDict, deque
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from typing import List
import itertools
import math
import heapq
import string
import random
(MIN, MAX, MOD) = (-1061109567, 1061109567, 1000000007)
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
for _ in range(N()):
	s = input()
	cnt = Counter(s)
	vis = [0] * 26
	n = len(s)
	res = []
	for i in range(n):
		cnt[s[i]] -= 1
		if not vis[ord(s[i]) - ord('a')]:
			while res and res[-1] < s[i] and (cnt[res[-1]] > 0):
				vis[ord(res[-1]) - ord('a')] = 0
				res.pop()
			res += s[i]
			vis[ord(s[i]) - ord('a')] = 1
	print(''.join(res))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	s = input().strip()
	n = len(s)
	freq = {}
	check = {}
	for i in s:
		freq[i] = freq.get(i, 0) + 1
		check[i] = 0
	stack = []
	for i in range(n):
		freq[s[i]] -= 1
		if check[s[i]]:
			continue
		while len(stack) and s[i] > stack[-1] and freq[stack[-1]]:
			x = stack.pop()
			check[x] = 0
		stack.append(s[i])
		check[s[i]] = 1
	print(''.join(stack))


from bisect import bisect_left
from collections import defaultdict
from itertools import accumulate
from sys import stdin, gettrace
ORDA = ord('a')
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()
ALPHABET = 'abcdefghijlmnopqrstuvwxyz'

def solve():
	aa = list(input())
	res = []
	rset = set()
	csets = list(accumulate([set()] + aa[::-1], func=lambda s, v: s | {v}))
	csets = csets[:0:-1]
	cset = csets[0].copy()
	tstart = 0

	def can(c):
		nonlocal tstart
		p = aa.index(c, tstart)
		if cset == csets[p] - rset:
			tstart = p
			return True
		else:
			return False
	while cset:
		c = next((c for c in sorted(cset, reverse=True) if can(c)))
		res.append(c)
		cset.remove(c)
		rset.add(c)
	print(''.join(res))

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def solve():
	s = input()
	exists = [[]] * 26
	for i in range(len(s) - 1, -1, -1):
		ch = ord(s[i]) - ord('a')
		if exists[ch]:
			exists[ch].append(i)
		else:
			exists[ch] = [i]
	start = 0
	while True:
		something_happened = False
		for use in range(25, -1, -1):
			if not exists[use]:
				continue
			where = exists[use][-1]
			suitable = True
			for occur in exists:
				if occur and occur[0] < where:
					suitable = False
					break
			if suitable:
				print(s[where], end='')
				exists[use] = []
				start = where + 1
				for c in range(26):
					while exists[c] and exists[c][-1] < start:
						exists[c].pop()
				something_happened = True
				break
		if not something_happened:
			break
	print()

def main():
	t = int(input())
	while t:
		solve()
		t -= 1
main()


t = int(input())
for test in range(1, t + 1):
	s = list(input())
	store = [0 for _ in range(len(s))]
	curr = 0
	visited = set()
	last_seen = {}
	for (idx, ch) in enumerate(s[::-1]):
		if ch not in visited:
			curr += 1
			visited.add(ch)
		store[-idx - 1] = curr
		if ch not in last_seen:
			last_seen[ch] = len(s) - 1 - idx
	res = []
	sel_idx = 0
	visited = set()
	while curr > 0:
		choose = None
		choose_idx = None
		for idx in range(sel_idx, len(s)):
			item = store[idx]
			if item == curr and s[idx] not in visited:
				if choose is None or s[idx] > choose:
					choose = s[idx]
					choose_idx = idx
		res.append(choose)
		visited.add(choose)
		sel_idx = choose_idx + 1
		new_store = []
		curr -= 1
		for (idx, item) in enumerate(store):
			if idx <= last_seen[choose]:
				new_store.append(item - 1)
			else:
				new_store.append(item)
		store = new_store
	print(''.join(res))


T = int(input())
r = 1
while r <= T:
	s = input()
	n = len(s)
	lastappear = [0] * 26
	for i in range(n):
		lastappear[ord(s[i]) - 97] = i
	stack = []
	already = [False] * 26
	for i in range(n):
		if already[ord(s[i]) - 97]:
			continue
		while stack and ord(stack[-1]) <= ord(s[i]):
			if i > lastappear[ord(stack[-1]) - 97]:
				break
			c = stack.pop()
			already[ord(c) - 97] = False
		if not already[ord(s[i]) - 97]:
			stack.append(s[i])
			already[ord(s[i]) - 97] = True
	ans = ''.join(stack)
	print(ans)
	r += 1


t = int(input())
for _ in range(t):
	a = list(input())
	trans = lambda x: ord(x) - 97
	d = {}
	for i in a:
		d[trans(i)] = 0
	for i in range(len(a)):
		d[trans(a[i])] = i
	used = [False] * 26
	ans = [a[0]] + [''] * len(a)
	used[trans(a[0])] = True
	p = 0
	for i in range(1, len(a)):
		if used[trans(a[i])]:
			continue
		while p >= 0 and ans[p] < a[i] and (d[trans(ans[p])] > i):
			used[trans(ans[p])] = False
			ans[p] = ''
			p -= 1
		p += 1
		ans[p] = a[i]
		used[trans(ans[p])] = True
	print(''.join(ans))


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import defaultdict

class Solution:

	def removeDuplicateLetters(self, s: str) -> str:
		lastloc = {c: i for (i, c) in enumerate(s)}
		stack = ['{']
		vis = set()
		for (i, c) in enumerate(s):
			if c in vis:
				continue
			while c > stack[-1] and lastloc[stack[-1]] > i:
				vis.remove(stack.pop())
			stack.append(c)
			vis.add(c)
		ans = ''.join(stack[1:])
		print(ans)
for i in range(ii1()):
	Solution().removeDuplicateLetters(is1())


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
	S = input().rstrip()
	d = {i: v for (v, i) in enumerate(S)}
	res = []
	seen = set()
	for (i, s) in enumerate(S):
		if s not in seen:
			while res and s > res[-1] and (d[res[-1]] > i):
				seen.discard(res.pop())
			res.append(s)
			seen.add(s)
	print(''.join(res))
t = int(input())
for _ in range(t):
	solve()


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	last = {}
	for j in range(n):
		last[s[j]] = j
	ans = [s[0]]
	visit = set()
	visit.add(s[0])
	for j in range(1, n):
		if s[j] in visit:
			continue
		while len(ans) and ans[-1] < s[j] and (last[ans[-1]] >= j):
			visit.remove(ans[-1])
			ans.pop()
		ans.append(s[j])
		visit.add(s[j])
	print(''.join(ans))


import sys
from sys import stdin
tt = int(stdin.readline())
alp = 'abcdefghijklmnopqrstuvwxyz'
ANS = []
for loop in range(tt):
	s = list(stdin.readline()[:-1])
	n = len(s)
	alis = []
	adic = {}
	use = [False] * n
	for i in s:
		if i not in adic:
			adic[i] = True
			alis.append(i)
	alis.sort()
	anum = len(alis)
	l = -1
	for i in range(anum):
		nmax = None
		ntype = 0
		dic = {}
		for j in range(n - 1, l, -1):
			if not adic[s[j]]:
				continue
			if s[j] not in dic:
				dic[s[j]] = 1
				ntype += 1
			if ntype + i >= anum:
				if nmax == None:
					nmax = j
				elif s[j] >= s[nmax]:
					nmax = j
		use[nmax] = True
		l = nmax
		adic[s[nmax]] = False
	ans = []
	for i in range(n):
		if use[i]:
			ans.append(s[i])
	ANS.append(''.join(ans))
print('\n'.join(ANS))


import io
import os
from collections import Counter, defaultdict, deque

def solve(s):
	indices = defaultdict(deque)
	for (i, x) in enumerate(s):
		o = ord(x) - ord('a')
		indices[o].append(i)
	suff = [0]
	for x in s[::-1]:
		o = ord(x) - ord('a')
		suff.append(suff[-1] | 1 << o)
	neededMask = suff[-1]
	n = len(s)
	ans = []
	while neededMask:
		for i in reversed(range(26)):
			if 1 << i & neededMask:
				pos = indices[i][0]
				reachable = suff[n - 1 - pos]
				remainingNeeded = neededMask - (1 << i)
				if reachable & remainingNeeded == remainingNeeded:
					ans.append(chr(ord('a') + i))
					neededMask -= 1 << i
					del indices[i]
					for (k, v) in indices.items():
						while v and v[0] < pos:
							v.popleft()
						assert v
					break
		else:
			assert False
	return ''.join(ans)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	S = input().decode().rstrip()
	ans = solve(S)
	print(ans)


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')
eps = 10 ** (-10)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def ord_chr(array, fanc):
	if fanc == 0:
		res = [ord(s) - ord('a') for s in array]
		return res
	if fanc == 1:
		res = [chr(i + ord('a')) for i in array]
		res = ''.join(res)
		return res
T = getN()
for _ in range(T):
	S = ord_chr(list(input()), 0)
	N = len(S)
	l = defaultdict(list)
	for i in range(N - 1, -1, -1):
		l[S[i]].append(i)
	prev = [[key, value] for (key, value) in l.items()]
	prev.sort(reverse=True)
	now = -1
	ans = []
	while prev:
		next = []
		for i in range(len(prev)):
			while prev[i][1] and prev[i][1][-1] <= now:
				prev[i][1].pop()
			if prev[i][1]:
				next.append(prev[i])
		for i in range(len(next)):
			for j in range(len(next)):
				if next[i][1][-1] > next[j][1][0]:
					break
			else:
				now = next[i][1][-1]
				ans.append(next[i][0])
				next = [next[j] for j in range(len(next)) if j != i]
				prev = next
				break
	print(ord_chr(ans, 1))


import os
import sys
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict
from heapq import heapify, heappush, heappop

def solve(S):
	N = len(S)
	rightmost = {char: i for (i, char) in enumerate(S)}
	stack = []
	seen = set()
	for (i, char) in enumerate(S):
		if char in seen:
			continue
		while stack and char > stack[-1] and (rightmost[stack[-1]] > i):
			seen.remove(stack.pop())
		stack.append(char)
		seen.add(char)
	return ''.join(stack)

def main():
	for _ in range(inInt()):
		outStr(solve(inStr()))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inInt = lambda : int(input())
inLst = lambda : list(map(int, input().split()))
inStr = lambda : list(input())
inVar = lambda : map(int, input().split())
outInt = lambda n: sys.stdout.write(str(n) + '\n')
outLst = lambda lst: sys.stdout.write(' '.join(map(str, lst)) + '\n')
outStr = lambda s: sys.stdout.write(''.join(s) + '\n')
main()


from collections import deque
t = int(input())
for _ in range(t):
	string = str(input())
	letters = set()
	for s in string:
		letters.add(s)
	letters = sorted(list(letters), key=lambda x: ord(x))
	letters = deque(reversed(letters))
	answer = []
	indexes = [deque([]) for i in range(26)]
	for (index, l) in enumerate(string):
		indexes[ord(l) - ord('a')].append(index)
	temp_queue = []
	answer = []
	while letters:
		current_char = letters.popleft()
		is_viable = True
		for other_letter in letters:
			if other_letter != current_char:
				if len(indexes[ord(other_letter) - ord('a')]) > 0 and indexes[ord(other_letter) - ord('a')][-1] < indexes[ord(current_char) - ord('a')][0]:
					is_viable = False
					break
		if is_viable:
			answer.append(current_char)
			while temp_queue:
				letters.appendleft(temp_queue.pop())
			index_upto = indexes[ord(current_char) - ord('a')][0]
			for val in indexes:
				while len(val) > 0 and val[0] < index_upto:
					val.popleft()
		else:
			temp_queue.append(current_char)
		if not letters:
			while temp_queue:
				letters.appendleft(temp_queue.pop())
	print(''.join(answer))