You are given a string $s$ consisting of lowercase letters of the English alphabet. You must perform the following algorithm on $s$:

Let $x$ be the length of the longest prefix of $s$ which occurs somewhere else in $s$ as a contiguous substring (the other occurrence may also intersect the prefix). If $x = 0$, break. Otherwise, remove the first $x$ characters of $s$, and repeat.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".

For instance, if we perform the algorithm on $s =$ "abcabdc",

Initially, "ab" is the longest prefix that also appears somewhere else as a substring in $s$, so $s =$ "cabdc" after $1$ operation.

Then, "c" is the longest prefix that also appears somewhere else as a substring in $s$, so $s =$ "abdc" after $2$ operations.

Now $x=0$ (because there are no non-empty prefixes of "abdc" that also appear somewhere else as a substring in $s$), so the algorithm terminates.

Find the final state of the string after performing the algorithm.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

This is followed by $t$ lines, each containing a description of one test case. Each line contains a string $s$. The given strings consist only of lowercase letters of the English alphabet and have lengths between $1$ and $2 \cdot 10^5$ inclusive.

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


-----Output-----

For each test case, print a single line containing the string $s$ after executing the algorithm. It can be shown that such string is non-empty.


-----Examples-----

Input
6
abcabdc
a
bbbbbbbbbb
codeforces
cffcfccffccfcffcfccfcffccffcfccf
zyzyzwxxyyxxyyzzyzzxxwzxwywxwzxxyzzw
Output
abdc
a
b
deforces
cf
xyzzw


-----Note-----

The first test case is explained in the statement.

In the second test case, no operations can be performed on $s$.

In the third test case,

Initially, $s =$ "bbbbbbbbbb".

After $1$ operation, $s =$ "b".

In the fourth test case,

Initially, $s =$ "codeforces".

After $1$ operation, $s =$ "odeforces".

After $2$ operations, $s =$ "deforces".

Source: codeforces | Difficulty: EASY
Tags: String algorithms


Solutions:
from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		d = dd(int)
		s = rs()
		for i in s:
			d[i] += 1
		for i in range(len(s)):
			if d[s[i]] == 1:
				x = i
				break
			d[s[i]] -= 1
		print(s[x:])
main()


import sys

def solve():
	inp = sys.stdin.readline
	s = inp().strip()
	d = dict()
	for i in s:
		d[i] = d.get(i, 0) + 1
	for i in range(len(s)):
		c = s[i]
		if d[c] == 1:
			print(s[i:])
			return
		d[c] -= 1

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def solve():
	d = {}
	for i in x:
		d[i] = 0
	s = len(d)
	s2 = 0
	n = x[:]
	for i in range(len(x) - 1, -1, -1):
		if d[x[i]] == 0 or s2 != s:
			s2 -= d[x[i]]
			d[x[i]] = 1
			s2 += d[x[i]]
		else:
			n = x[i + 1:]
			break
	return n
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	x = input().strip()
	print(solve())


from sys import stdin
ans = []
for _ in range(int(input())):
	s = list(input())
	st = set(s)
	for i in range(len(s) - 1, -1, -1):
		if s[i] in st:
			st.remove(s[i])
			if len(st) == 0:
				ans.append(''.join(s[i:]))
				break
print('\n'.join(ans))


cases = []
for i in range(int(input())):
	cases.append(input())
for case in cases:
	dict = {}
	ind = len(case) - 1
	for i in range(len(case) - 1, -1, -1):
		if case[i] in dict:
			dict[case[i]] = dict[case[i]] + 1
		else:
			dict[case[i]] = 1
			ind = i
	print(case[ind:])


def main():
	from sys import stdin, stdout
	rl = stdin.readline
	wl = stdout.write
	for _ in range(int(rl())):
		s = rl().strip()
		a = [-1] * 26
		for (i, x) in enumerate(s[::-1]):
			if a[ord(x) - ord('a')] == -1:
				a[ord(x) - ord('a')] = i
		m = max(a)
		wl(s[len(s) - m - 1:] + '\n')
main()


t = int(input())
for _ in range(t):
	s = input()
	p = {c: i for (i, c) in enumerate(s)}
	res = s[min(p.values()):]
	print(res)


import sys
import math
from collections import deque
import heapq

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

def mpp():
	return map(int, inp().split())

def lis():
	return list(mpp())

def pr(obj):
	sys.stdout.write(obj + '\n')

def sol(s):
	di = {}
	for i in s:
		if di.get(i):
			di[i] += 1
		else:
			di[i] = 1
	j = 0
	while j < len(s):
		di[s[j]] -= 1
		if di[s[j]] == 0:
			return s[j:]
		j += 1
	return ''

def main():
	t = int(inp())
	for _ in range(t):
		s = inp()
		pr(sol(s))
main()


import sys
input = sys.stdin.readline

def solve(s):
	n = len(s)
	cnt = {}
	for i in range(n):
		if s[i] not in cnt:
			cnt[s[i]] = 0
		cnt[s[i]] += 1
	for i in range(n):
		if cnt[s[i]] == 1:
			print(s[i:])
			return
		cnt[s[i]] -= 1
for _ in range(int(input())):
	s = input().strip()
	solve(s)


def test(arr):
	mp = {}
	for i in arr:
		if i not in mp:
			mp[i] = 1
		else:
			mp[i] += 1
	index = -1
	for i in range(len(arr)):
		index = i
		if mp[arr[i]] > 1:
			mp[arr[i]] -= 1
		else:
			break
	return arr[index:]
t = int(input())
for i in range(t):
	s = input()
	print(test(s))


from collections import deque, Counter
import sys
dic_temp = {}
iT = int(input())
for _ in range(iT):
	s = sys.stdin.readline().strip()
	dic_temp = dict(Counter(s))
	for i in range(len(s)):
		if dic_temp[s[i]] == 1:
			print(s[i:])
			break
		else:
			dic_temp[s[i]] -= 1


import sys

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

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

def main():
	for _ in range(int(input())):
		s = input()
		d = dict()
		for c in s:
			if c not in d:
				d[c] = 1
			else:
				d[c] += 1
		i = 0
		for c in s:
			if d[c] >= 2:
				d[c] -= 1
				i += 1
			else:
				break
		print(s[i:])
main()


from collections import Counter
import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def solve():
	s = input().strip('\n')
	n = len(s)
	if n == 1:
		return s
	l = Counter(s)
	for i in range(n):
		if l[s[i]] > 1:
			l[s[i]] -= 1
		else:
			return s[i:]
	return s
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	s = input()
	l = len(s)
	for i in range(l):
		if s.find(s[i], i + 1) == -1:
			print(s[i:])
			break


for _ in range(int(input())):
	s = input()
	x = set(s)
	print(s[min((s.rindex(y) for y in x)):])


for _ in range(int(input())):
	s = input()
	hashset = set(s)
	l = len(hashset)
	n = len(s)
	x = set()
	for i in range(n - 1, -1, -1):
		x.add(s[i])
		if len(x) == l:
			print(s[i:])
			break


def prefix_removal(s):
	freq = dict()
	for ele in s:
		if ele in freq:
			freq[ele] += 1
		else:
			freq[ele] = 1
	i = 0
	while i < len(s):
		if freq[s[i]] == 1:
			break
		freq[s[i]] -= 1
		i += 1
	print(s[i:])
test = int(input())
while test:
	s = input()
	prefix_removal(s)
	test -= 1


from collections import defaultdict

def solve():
	s = input()
	d = defaultdict(set)
	for (i, v) in enumerate(s):
		d[v].add(i)
	for (i, v) in enumerate(s):
		d[v].remove(i)
		if not d[v]:
			return s[i:]

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


t = int(input())
while t:
	t -= 1
	s = input()
	l = list(s)
	rev = l[::-1]
	s1 = set(l)
	m = 0
	for i in s1:
		temp = rev.index(i)
		if temp > m:
			m = temp
	print(s[len(s) - m - 1:])


def solve(s):
	mp = {}
	for i in s:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
	for i in range(len(s)):
		if mp[s[i]] == 1:
			return s[i:]
		else:
			mp[s[i]] -= 1
T = int(input())
for i in range(T):
	s = input()
	print(solve(s))


from collections import defaultdict
t = int(input())

def recur(s):
	(n, cnt) = (len(s), defaultdict(int))
	for c in s:
		cnt[c] += 1
	for i in range(n):
		if cnt[s[i]] == 1:
			return s[i:]
		cnt[s[i]] -= 1
for _ in range(t):
	s = input()
	print(recur(s))


for _ in range(int(input())):
	s = input()
	d = {}
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in range(len(s)):
		d[s[i]] -= 1
		if d[s[i]] == 0:
			print(s[i:])
			break


t = int(input())
while t > 0:
	t -= 1
	s = input()[::-1]
	p = 0
	for c in set(s):
		p = max(p, s.index(c))
	print(s[:p + 1][::-1])


import math
for k in range(int(input())):
	s = input()
	if len(s) == 1:
		print(s)
	else:
		d = dict()
		for k in range(len(s)):
			d[s[k]] = k
		l = []
		for k in d:
			l.append(d[k])
		m = min(l)
		print(s[m:])


def solve(x):
	n = len(x)
	set_x = set(x)
	count = 0
	for i in range(n - 1, -1, -1):
		a = x[i]
		count += 1
		if a in set_x:
			set_x -= {a}
			if set_x == set():
				break
	print(x[n - count:n])

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


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in wtf[1:]:
	S = t
	N = len(S)
	Fs = dict()
	for s in S:
		if s not in Fs:
			Fs[s] = 1
		else:
			Fs[s] += 1
	for i in range(N):
		if Fs[S[i]] - 1 == 0:
			print(S[i:])
			break
		Fs[S[i]] -= 1


def main():
	times = int(input())
	for _ in range(times):
		data = input()
		size = len(data)
		flat = {}
		for i in range(size):
			if data[i] in flat:
				flat[data[i]] += 1
			else:
				flat[data[i]] = 1
		ans = 0
		for i in range(size):
			if flat[data[i]] == 1:
				ans = i
				break
			else:
				flat[data[i]] -= 1
		print(data[ans:])
main()


for inh in range(int(input())):
	s = input()
	n = len(s) - 1
	k = set()
	while n >= 0:
		if s[n] not in k:
			ans = n
			k.add(s[n])
		n -= 1
	print(s[ans:])


t = int(input())
for _ in range(t):
	string = input()
	char_dict = {}
	for item in string:
		if char_dict.get(item) is None:
			char_dict[item] = 1
		else:
			char_dict[item] += 1
	count = 0
	while char_dict[string[count]] >= 2:
		char_dict[string[count]] -= 1
		count += 1
	print(string[count:])


from collections import defaultdict
t = int(input())
for test in range(t):
	s = input().strip()
	freq = defaultdict(int)
	for i in s:
		freq[i] += 1
	res = 0
	for i in s:
		if freq[i] == 1:
			break
		freq[i] -= 1
		res += 1
	print(s[res:])


for _ in range(int(input())):
	s = input()
	l = len(s)
	d = set()
	for i in range(l - 1, -1, -1):
		if s[i] not in d:
			ans = s[i:]
			d.add(s[i])
	print(ans)


def solve(s):
	string_array = list(s)
	char_list = list(set(string_array))
	occ_list = []
	for char in char_list:
		occ_list.append(s.rfind(char))
	min_index = min(occ_list)
	return s[min_index:]
n = int(input().strip())
for i in range(n):
	s = input().replace('\n', '')
	print(solve(s))


t = int(input())
for _ in range(0, t):
	a = input()
	b = {}
	for ele in a:
		if ele in b:
			b[ele] += 1
		else:
			b[ele] = 1
	f = ''
	for ele in range(len(a)):
		if b[a[ele]] == 1:
			f = a[ele:]
			break
		else:
			b[a[ele]] -= 1
	print(f)


t = int(input())
for _ in range(t):
	s = input()
	dic = {}
	for c in s:
		dic[c] = dic.get(c, 0) + 1
	i = 0
	while dic[s[i]] > 1:
		dic[s[i]] -= 1
		i += 1
	print(s[i:])


for i in range(int(input())):
	s = input()
	mp = {}
	for x in s:
		if x in mp:
			mp[x] += 1
		else:
			mp[x] = 1
	i = 0
	while mp[s[i]] > 1:
		mp[s[i]] -= 1
		i += 1
	print(s[i:])


def inp():
	return int(input())
for _ in range(inp()):
	s = input()
	d = {}
	idx = len(s) - 1
	for c in s[::-1]:
		if d.get(c, None) is None:
			d[c] = idx
		idx -= 1
	print(s[min(d.values()):])


def find(s):
	sdict = {}
	for e in s:
		if sdict.get(e, 0) > 0:
			sdict[e] += 1
		else:
			sdict[e] = 1
	lists = list(s)
	lists.reverse()
	while sdict[lists[-1]] > 1:
		x = lists.pop()
		sdict[x] -= 1
	lists.reverse()
	return ''.join(lists)
cases = int(input())
for _ in range(cases):
	s = input()
	print(find(s))


t = int(input())
for _ in range(t):
	s = input()
	av = ord('a')
	n = [0] * 26
	for i in range(len(s)):
		n[ord(s[i]) - 97] = i
	for j in range(len(s)):
		if j == n[ord(s[j]) - 97]:
			break
	print(s[j:])


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
import heapq
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 998244353

def func():
	s = strng()
	n = len(s)
	d = {}
	for i in range(n):
		if s[i] in d:
			d[s[i]] += 1
		else:
			d[s[i]] = 1
	for i in range(n):
		if d[s[i]] == 1:
			return s[i:]
		d[s[i]] -= 1
t = inp()
for i in range(t):
	print(func())


t = int(input())
while t:
	s = input()
	curr = 0
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	curr = 0
	for i in s:
		if d[i] > 1:
			d[i] -= 1
			curr += 1
		else:
			break
	print(s[curr:])
	t -= 1


for _ in range(int(input())):
	S = input()
	k = len(S)
	A = []
	L = k
	for i in range(L - 1, -1, -1):
		if S[i] not in A:
			A.append(S[i])
			k = i
	print(S[k:])


t = int(input())
for k in range(t):
	st = input()
	ans = ''
	d = {}
	n = len(st)
	for ele in st:
		d[ele] = d.get(ele, 0) + 1
	for i in range(n):
		if d[st[i]] == 1:
			ans = st[i:]
			break
		else:
			d[st[i]] -= 1
	print(ans)


for iii in range(int(input())):
	s = input()
	e = {i: 0 for i in s}
	a = len(s)
	for i in s:
		e[i] += 1
	for i in range(len(s)):
		if e[s[i]] == 1:
			a = i
			break
		e[s[i]] -= 1
	print(s[a:len(s)])


def f():
	s = input()
	if len(set(s)) == 0:
		return s[0]
	d = {}
	for i in s:
		d[i] = d.get(i, 0) + 1
	for i in range(len(s)):
		if d[s[i]] == 1:
			return s[i:]
		d[s[i]] -= 1
n = int(input())
for _ in range(n):
	print(f())


from collections import defaultdict
for _ in range(int(input())):
	s = input()
	d = defaultdict(int)
	for i in s:
		d[i] += 1
	c = 0
	for i in s:
		if d[i] == 1:
			break
		else:
			d[i] -= 1
			c += 1
	print(s[c:])


def solve():
	s = input()
	x = set(s)
	lowest = len(s) - max([s[::-1].index(y) for y in x]) - 1
	print(s[lowest:])
for tc in range(int(input())):
	solve()


def solve():
	n = input()
	dic = {i: n.count(i) for i in set(list(n))}
	i = 0
	for i in range(len(n)):
		if dic[n[i]] > 1:
			dic[n[i]] -= 1
			i += 1
		else:
			break
	print(n[i:])
tst = int(input())
for i in range(tst):
	solve()


def solve():
	s = input()
	d = dict()
	for i in s:
		if i not in d:
			d[i] = 0
		d[i] += 1
	fl = 1
	ans = []
	for i in s:
		d[i] -= 1
		if fl and d[i] != 0:
			continue
		else:
			ans.append(i)
			fl = 0
	print(''.join(ans))

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


t = int(input())
for _ in range(0, t):
	s = input()
	dict1 = {}
	for i in range(0, len(s)):
		ch = s[i]
		if ch in dict1:
			dict1[ch] += 1
		else:
			dict1[ch] = 1
	ind = 0
	for i in range(0, len(s)):
		ch = s[i]
		if dict1[ch] > 1:
			dict1[ch] -= 1
		else:
			ind = i
			break
	s1 = s[i:]
	print(s1)


for _ in range(int(input())):
	s = input()
	d = {}
	for i in s:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = ''
	f = 0
	pos = 0
	for i in s:
		if d[i] > 1:
			d[i] -= 1
			pos = pos + 1
		elif d[i] == 1:
			print(s[pos:])
			break


def prefixRemoval(targetStr):
	temp = targetStr
	charList = [len(targetStr) for i in range(26)]
	for i in range(0, len(targetStr)):
		charList[ord(targetStr[i]) - 97] = i
	return targetStr[min(charList):]
for i in range(int(input())):
	targetStr = str(input())
	print(prefixRemoval(targetStr))


for el in range(int(input())):
	(s, l) = (input(), [])
	for i in range(1, len(s) + 1):
		if s[-i] not in l:
			last_up = i
			l.append(s[-i])
	print(s[len(s) - last_up:])


t = int(input(''))
for z in range(t):
	s = input('')
	b = set(s)
	d = dict()
	for i in b:
		if i not in d:
			d[i] = s.rindex(i)
	c = 1000000
	for j in d:
		if d[j] < c:
			c = d[j]
	print(s[c:])


def solution(string):
	counter = {_: 0 for _ in 'abcdefghijklmnopqrstuvwxyz'}
	for ch in string:
		counter[ch] += 1
	for i in range(len(string)):
		if counter[string[i]] == 1:
			return string[i:]
		elif counter[string[i]] > 1:
			counter[string[i]] -= 1
for _ in range(int(input())):
	string = input()
	print(solution(string))


tc = int(input())
for _ in range(tc):
	s = input()
	counter = dict.fromkeys(list('abcdefghijklmnopqrstuvwxyz'), 0)
	for c in s:
		counter[c] += 1
	i = 0
	while i < len(s) and counter[s[i]] > 1:
		counter[s[i]] -= 1
		i += 1
	print(s[i:])


for i in range(int(input())):
	s = input()
	dct = dict()
	num = 0
	for i in s:
		num += 1
		dct[i] = num
	arr = []
	for i in dct.keys():
		arr.append([i, dct[i]])
	arr.sort(key=lambda x: x[1])
	print(s[arr[0][1] - 1:])


t = int(input())
for i in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		d[s[i]] = d.get(s[i], 0) + 1
	o = ''
	for i in range(len(s)):
		if d[s[i]] > 1:
			d[s[i]] -= 1
		else:
			o += s[i:len(s)]
			break
	print(o)


def haha(s):
	l = list(s)
	sl = l[::-1]
	se = list(set(l))
	r = l[::-1]
	d = {}
	for i in se:
		d[i] = r.index(i)
	t = max(d.values())
	mg = sl[:t + 1]
	gm = mg[::-1]
	return ''.join(gm)
for i in range(int(input())):
	n = input()
	x = haha(n)
	print(x)


t = int(input())
for _ in range(t):
	s = input()
	has = {}
	for i in s:
		if i not in has:
			has[i] = 1
		else:
			has[i] += 1
	res = ''
	i = 0
	while i < len(s):
		if has[s[i]] > 1:
			has[s[i]] -= 1
		else:
			break
		i += 1
	res = res + s[i:]
	print(res)


for _ in range(int(input())):
	a = input()
	dic = {}
	for i in a:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	idx = -1
	for i in range(len(a)):
		if dic[a[i]] > 1:
			dic[a[i]] -= 1
			idx = i
		else:
			break
	s = ''
	for i in range(idx + 1, len(a), 1):
		s += a[i]
	print(s)


t = int(input())
for i in range(t):
	s = list(input())
	d = {}
	k = 0
	for i in s:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	for i in s:
		if d[i] > 1:
			k = k + 1
			d[i] -= 1
		else:
			break
	if k == len(s):
		print(s[0])
	else:
		print(''.join(s[k:]))


for _ in range(int(input())):
	inp = input()
	count = {x: 0 for x in inp}
	for item in inp:
		count[item] += 1
	for (i, char) in enumerate(inp):
		if count[char] > 1:
			count[char] -= 1
		else:
			break
	print(inp[i:])


for _ in range(int(input())):
	s = input()
	c = {}
	for x in s:
		c[x] = c.get(x, 0) + 1
	i = 0
	while i < len(s):
		if c[s[i]] > 1:
			c[s[i]] -= 1
			i += 1
		else:
			break
	print(s[i:])


t = int(input())
for i in range(t):
	s = input()
	d = {}
	for i in range(len(s)):
		d[s[i]] = i
	m = float('inf')
	for i in d.values():
		m = min(i, m)
	print(s[m:])


import string
t = int(input())
for i in range(t):
	rpos = dict.fromkeys(string.ascii_lowercase, 0)
	text = input()
	for i in range(len(text)):
		rpos[text[i]] = i + 1
	pos = min([i for i in rpos.values() if i != 0])
	print(text[pos - 1:])


for _ in range(int(input())):
	a = input()
	n = len(a)
	d = {}
	for i in range(n):
		try:
			d[a[i]] += 1
		except:
			d[a[i]] = 1
	for i in range(n):
		if d[a[i]] == 1:
			print(a[i:])
			break
		else:
			d[a[i]] -= 1


for _ in range(int(input())):
	s = input()
	idx = 0
	mp = {}
	for i in range(len(s)):
		if s[i] in mp:
			mp[s[i]] += 1
		else:
			mp[s[i]] = 1
	for i in range(len(s)):
		if mp[s[i]] == 1:
			idx = i
			break
		else:
			mp[s[i]] -= 1
	print(s[idx:])


t = int(input())
for _ in range(t):
	s = input()
	amounts = {}
	for ch in s:
		amounts[ch] = amounts.get(ch, 0) + 1
	for i in range(len(s)):
		if amounts[s[i]] == 1:
			print(s[i:])
			break
		amounts[s[i]] -= 1


t = int(input())
alfa = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(t):
	s = input()
	las = len(s)
	for i in alfa:
		k = s.rfind(i)
		if k < las and k != -1:
			las = k
	print(s[las:])


from collections import Counter
for _ in range(int(input())):
	s = input()
	freq = Counter(s)
	for i in range(len(s)):
		if freq[s[i]] == 1:
			print(s[i:])
			break
		freq[s[i]] -= 1


from collections import Counter
for _ in range(int(input())):
	s = input()
	f = Counter(s)
	i = 0
	for item in s:
		if f[item] <= 1:
			break
		f[item] -= 1
		i += 1
	print(s[i:])


def solve(s):
	alphabet = 'abcdefghijklmnopqrstuvwxyz'
	a = dict(zip(alphabet, [s.count(i) for i in alphabet]))
	for (i, j) in enumerate(s):
		if a[j] <= 1:
			return s[i:]
		else:
			a[j] -= 1
for _ in range(int(input())):
	print(solve(input()))


n = int(input())
for i in range(n):
	t = input()
	lis = list(t)
	g = {}
	for j in lis:
		if j not in g:
			g[j] = 1
		else:
			g[j] = g[j] + 1
	tin = 0
	for k in range(len(lis)):
		if g[lis[k]] > 1:
			g[lis[k]] = g[lis[k]] - 1
		else:
			tin = k
			break
	print(t[tin:])


t = int(input())
for i in range(0, t):
	s = input()
	freq = [0] * 26
	index = 0
	for i in s:
		freq[ord(i) - 97] += 1
	for i in s:
		if freq[ord(i) - 97] == 1:
			break
		else:
			freq[ord(i) - 97] -= 1
			index += 1
	print(s[index:])


from collections import defaultdict as dd
for _ in range(int(input())):
	string = input().strip()
	dk = dd(int)
	for x in string:
		dk[x] += 1
	y = 0
	for x in string:
		if dk[x] == 1:
			break
		dk[x] -= 1
		y += 1
	print(string[y:])


import sys
from math import *
for _ in range(int(input())):
	s = input()
	h = {}
	k = -1
	for i in s:
		h[i] = h.get(i, 0) + 1
	for i in range(len(s)):
		if h[s[i]] >= 2:
			h[s[i]] -= 1
		else:
			print(s[i:])
			break


for _ in range(int(input())):
	s = list(str(input()))
	dict = {}
	for i in s:
		if i not in dict:
			dict[i] = 1
		else:
			dict[i] += 1
	for i in range(len(s)):
		if dict[s[i]] > 1:
			dict[s[i]] -= 1
			s[i] = ''
		else:
			break
	print(''.join(s))


import math

def Solve():
	s = input()
	a = [0 for i in range(len(s))]
	dic = {}
	for i in range(len(a) - 1, -1, -1):
		if dic.get(s[i]) == None:
			dic[s[i]] = 1
		else:
			dic[s[i]] = dic[s[i]] + 1
		a[i] = dic[s[i]]
	for i in range(len(a)):
		if a[i] == 1:
			break
	print(s[i:])
q = int(input())
while q > 0:
	Solve()
	q = q - 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	x = set([])
	j = 0
	for i in range(n):
		if s[n - i - 1] not in x:
			j = n - i - 1
		x.add(s[n - i - 1])
	print(s[j:])


l1 = [chr(i) for i in range(97, 123)]
l2 = [0] * 26
for _ in range(int(input())):
	d = dict(zip(l1, l2))
	s = input()
	k = len(s)
	for i in range(k):
		d[s[i]] += 1
	a = 0
	for i in range(k):
		if d[s[i]] > 1:
			d[s[i]] -= 1
		else:
			a = i
			break
	print(s[a:])


import sys, bisect, collections, itertools
for _ in range(int(input())):
	x = input()
	y = collections.Counter(x)
	for (i, a) in enumerate(x):
		if y[a] == 1:
			print(x[i:])
			break
		else:
			y[a] -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	ch = [0] * 26
	ans = s[-1]
	for i in range(n - 1, -1, -1):
		pos = ord(s[i]) - ord('a')
		ch[pos] += 1
		if ch[pos] == 1:
			ans = s[i:]
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	a = {}
	for i in range(len(s)):
		if s[i] in a:
			a[s[i]] += 1
		else:
			a[s[i]] = 1
	for i in range(len(s)):
		a[s[i]] -= 1
		if a[s[i]] == 0:
			print(s[i:])
			break


t = eval(input())
for _ in range(t):
	s = input()
	s1 = s[::-1]
	k = []
	d = []
	for i in range(len(s)):
		if s1[i] not in k:
			k.append(s1[i])
			d.append(1)
		else:
			d.append(0)
	d = d[::-1]
	for i in range(len(d)):
		if d[i] == 1:
			print(s[i:])
			break
	else:
		print(s)


t = int(input())
while t:
	s = input()
	ans = 0
	l = list(s)
	from collections import Counter
	d = Counter(l)
	for i in l:
		if d[i] != 1:
			ans = ans + 1
			d[i] = d[i] - 1
		else:
			print(''.join(s[ans:]))
			break
	t = t - 1


from collections import Counter, deque

def prefixRemoval(s):
	count = Counter(s)
	temp = deque(s)
	for word in s:
		if count[word] > 1:
			count[word] -= 1
			temp.popleft()
		else:
			break
	return ''.join(temp)
t = int(input())
for i in range(t):
	s = input()
	print(prefixRemoval(s))


from collections import Counter
for _ in range(int(input())):
	s = str(input())
	n = len(s)
	x = Counter(s)
	i = 0
	while i < n:
		if x[s[i]] > 1:
			x[s[i]] -= 1
			i += 1
		else:
			break
	print(s[i:])


for _ in range(int(input())):
	string = input()
	from collections import Counter
	freq = Counter(string)
	i = 0
	while string:
		if freq[string[i]] > 1:
			freq[string[i]] -= 1
			i += 1
		else:
			break
	print(string[i:])


from collections import Counter
for _ in range(int(input())):
	l = input()
	str = list(l)
	m = Counter(l)
	for i in range(len(str)):
		if m[str[i]] != 1:
			m[str[i]] -= 1
		else:
			print(''.join(str[i:]))
			break


t = int(input())
while t:
	s = input()
	l = [0] * 26
	a = 0
	for i in range(len(s)):
		l[ord(s[i]) - 97] += 1
	for i in range(len(s)):
		if l[ord(s[i]) - 97] == 1:
			a = i
			break
		else:
			l[ord(s[i]) - 97] -= 1
	print(s[a:])
	t -= 1