There was a string $s$ which was supposed to be encrypted. For this reason, all $26$ lowercase English letters were arranged in a circle in some order, afterwards, each letter in $s$ was replaced with the one that follows in clockwise order, in that way the string $t$ was obtained.

You are given a string $t$. Determine the lexicographically smallest string $s$ that could be a prototype of the given string $t$.

A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if:

in the first position where $a$ and $b$ differ, the string $a$ has a letter, that appears earlier in the alphabet than the corresponding letter in $b$.


-----Input-----

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

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the string $t$.

The next line contains the string $t$ of the length $n$, containing lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single line containing the lexicographically smallest string $s$ which could be a prototype of $t$.


-----Examples-----

Input
5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy
Output
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz


-----Note-----

In the first test case, we couldn't have the string "a", since the letter a would transit to itself. Lexicographically the second string "b" is suitable as an answer.

In the second test case, the string "aa" is not suitable, since a would transit to itself. "ab" is not suitable, since the circle would be closed with $2$ letters, but it must contain all $26$. The next string "ac" is suitable.

Below you can see the schemes for the first three test cases. The non-involved letters are skipped, they can be arbitrary placed in the gaps.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

String algorithms

Implementation

Greedy algorithms

Spanning trees


Solutions:
import string
for _ in range(int(input())):
	n = int(input())
	st = input()
	s = set()
	mp = {}
	letters = list(string.ascii_lowercase)

	def check(l, c):
		while l in mp:
			l = mp[l]
			if l == c:
				return True
		return False
	for c in st:
		if c in mp:
			continue
		for l in letters:
			if l == c or (l in mp and check(l, c) and (len(mp) < 25)):
				continue
			mp[c] = l
			letters.remove(l)
			break
	print(''.join((mp[c] for c in st)))


import sys
input = sys.stdin.readline
t = int(input())

def isgood(alpha, c1, c2):
	c = c2
	r = 0
	while c != 0:
		if c != c1:
			r = r + 1
			c = alpha[c]
		elif r < 25:
			return 0
		else:
			break
	return 1

def convert(s):
	new = ''
	for i in s:
		new += i
	return new
for i in range(t):
	n = int(input())
	c = list(input())
	c = c[:-1]
	alpha = {97: 0}
	for j in range(ord('b'), ord('z') + 1):
		alpha[j] = 0
	r = c
	letters = list(range(97, ord('z') + 1))
	for j in range(n):
		if alpha[ord(r[j])] != 0:
			r[j] = chr(alpha[ord(r[j])])
		else:
			for k in letters:
				if not isgood(alpha, ord(r[j]), k):
					continue
				alpha[ord(r[j])] = k
				r[j] = chr(k)
				letters.remove(k)
				break
	sys.stdout.write(convert(r) + '\n')


import os
import math
import collections
import bisect
import functools
import itertools
import string
from collections import deque

def solve(s):
	q = deque([c for c in string.ascii_lowercase])
	count_char = len(set([c for c in s]))
	d = {}
	res = ''
	for c in s:
		if c in d:
			res += d[c]
			continue
		tmp = []
		while q:
			if q[0] == c:
				tmp.append(q.popleft())
				continue
			x = q[0]
			count = 1
			while x in d and x != c:
				x = d[x]
				count += 1
			if x == c and count < 26:
				tmp.append(q.popleft())
			else:
				break
		c2 = q.popleft()
		res += c2
		d[c] = c2
		for x in tmp:
			q.appendleft(x)
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(solve(s))


def isCyclic(dct1, dct2, a, n):
	if n > 26:
		return False
	if a not in dct1:
		return False
	if dct1[a] in dct2:
		return True
	n += 1
	dct2[dct1[a]] = 0
	return isCyclic(dct1, dct2, dct1[a], n)
for t in range(int(input())):
	n = int(input())
	s = input()
	dct = {}
	st = set()
	ans = []
	lst = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	ind = 0
	for i in s:
		ind = 0
		if i in dct:
			ans.append(dct[i])
		elif len(lst) == 1:
			ans.append(lst[0])
			dct[i] = lst[0]
			st.add(lst[0])
			del lst[0]
		elif i in st:
			ind = 0
			while isCyclic(dct, {i: 0}, lst[ind], 0):
				ind += 1
			ans.append(lst[ind])
			dct[i] = lst[ind]
			st.add(lst[ind])
			del lst[ind]
		else:
			ind = 0
			while lst[ind] == i:
				ind += 1
			ans.append(lst[ind])
			dct[i] = lst[ind]
			st.add(lst[ind])
			del lst[ind]
	print(''.join(ans))


def solve():
	(N, s) = (int(input()), input())
	(visited, found, ans) = (set(), [-1] * 26, '')

	def helper(target):
		ans = 0
		stop = target
		while stop != -1:
			ans += 1
			stop = found[stop]
			if stop == target:
				return ans
		return -1
	for i in range(N):
		x = ord(s[i]) - ord('a')
		if found[x] != -1:
			ans += chr(found[x] + ord('a'))
			continue
		for j in range(26):
			if j in visited:
				continue
			if j == x:
				continue
			found[x] = j
			z = helper(j)
			if z != -1 and z != 26:
				continue
			else:
				visited.add(j)
				break
		ans += chr(found[x] + ord('a'))
	return ans
for _ in range(int(input())):
	print(solve())


def solve():
	n = int(input())
	t = input()
	gin = [-1] * 26
	gout = [-1] * 26
	s = ''
	next = 0
	for i in t:
		val = ord(i) - ord('a')
		if gin[val] > -1:
			s += chr(ord('a') + gin[val])
		else:
			for j in range(26):
				if gout[j] == -1 and j != val:
					(k, found, path) = (j, False, 0)
					while gin[k] > -1:
						k = gin[k]
						path += 1
						if k == val:
							found = True
							break
					if not found or path == 25:
						gin[val] = j
						gout[j] = val
						s += chr(ord('a') + j)
						break
	print(s)
test = int(input())
for i in range(test):
	solve()


l = list('abcdefghijklmnopqrstuvwxyz')

def dfs(d, s, j):
	if s == j:
		return 1
	while s:
		if j == d[s]:
			return 1
		s = d[s]
	return 0

def ss(s, n):
	d = {}
	d2 = {}
	for i in l:
		d[i] = 0
		d2[i] = ''
	for i in s:
		if d2[i] != '':
			continue
		for j in l:
			if i == j:
				continue
			if d[j] != 0:
				continue
			if dfs(d2, j, i) == 1:
				continue
			d2[i] = j
			d[j] = 1
			break
	for i in s:
		if d2[i] == '':
			for j in d:
				if d[j] == 0:
					d2[i] = j
	res = ''
	for i in s:
		res += d2[i]
	return res
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	print(ss(s, n))


ntestcases = int(input())
for i in range(ntestcases):
	tlen = int(input())
	t = list(input())
	sTotMap = {}
	tTosMap = {}
	nextLetter = 'a'
	answer = ['a'] * tlen
	j = 0

	def detectCycle(s, t):
		curr = t
		while curr in sTotMap:
			next = sTotMap[curr]
			if next == s:
				return True
			curr = next
		return False
	for c in t:
		if c in tTosMap:
			answer[j] = tTosMap[c]
			j += 1
			continue
		currLetter = nextLetter
		while currLetter in sTotMap or c == currLetter or (len(sTotMap) < 25 and detectCycle(currLetter, c)):
			currLetter = chr(ord(currLetter) + 1)
		if currLetter == nextLetter:
			nextLetter = chr(ord(nextLetter) + 1)
		answer[j] = currLetter
		j += 1
		sTotMap[currLetter] = c
		tTosMap[c] = currLetter
	print(''.join(answer))


q = int(input())

def char_position(letter):
	return ord(letter) - 97

def isCicular(a, b, g):
	curr = a
	while g[char_position(curr)] != None:
		curr = g[char_position(curr)]
	return curr == b
for _ in range(q):
	g = [None] * 26
	l = list('abcdefghijklmnopqrstuvwxyz')
	n = int(input())
	t = list(input())
	out = []
	first = None
	for i in range(n):
		k = 0
		idx = char_position(t[i])
		if g[idx] == None:
			if len(l) == 1:
				g[idx] = l.pop(0)
			else:
				while l[k] == t[i] or ((g[char_position(l[k])] != None and isCicular(l[k], t[i], g)) and k < len(l) - 1):
					k += 1
				g[idx] = l.pop(k)
		out.append(g[idx])
	print(''.join(out))


import math
import string
from typing import Optional

def mapped_read(cast):
	return map(cast, input().split())

def read_list(cast):
	return list(mapped_read(cast))

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

def check(g, start, t):
	cnt = 1
	curr = start
	while curr in g:
		cnt += 1
		curr = g[curr]
	return cnt == 26 or curr != t

def solve():
	(n,) = mapped_read(int)
	s = input()
	a = [chr(97 + i) for i in range(26)]
	prev = {}
	for c in s:
		if c not in prev:
			for i in a:
				if i != c and (i not in prev or check(prev, i, c)):
					prev[c] = i
					a.remove(i)
					break
		print(prev[c], end='')
	print()
one = False
for _ in range(1 if one else int(input())):
	solve()


def get_root(sss, i):
	if sss[i] != i:
		sss[i] = get_root(sss, sss[i])
	return sss[i]
for _ in range(int(input())):
	(_, sss) = (input(), list(range(26)))
	(s, letters, coding) = ([ord(c) - 97 for c in input()], [ord(c) - 97 for c in reversed(__import__('string').ascii_lowercase)], [-1] * 26)
	for char in s:
		if coding[char] == -1:
			j = len(letters) - 1
			u = get_root(sss, char)
			while j and get_root(sss, letters[j]) == u:
				j -= 1
			coding[char] = letters.pop(j)
			sss[sss[char]] = sss[coding[char]]
	print(''.join((chr(coding[c] + 97) for c in s)))


for _ in range(int(input())):
	n = int(input())
	t = list(map(lambda x: ord(x) - ord('a'), list(input())))
	next = [None] * 26
	prev = [None] * 26

	def ok(c, j):
		cnt = 1
		while next[j] != None:
			j = next[j]
			cnt += 1
		if c != j:
			return True
		return cnt == 26
	for (i, c) in enumerate(t):
		if next[c] == None:
			for j in range(26):
				if prev[j] == None and c != j and ok(c, j):
					next[c] = j
					prev[j] = c
					break
		t[i] = next[c]
	t = list(map(lambda x: chr(ord('a') + x), t))
	print(''.join(t))


def getResult(n, s):

	def check(edges_dict, i):
		if len(edges_dict.keys()) == 26:
			return False
		ori = i
		while i in edges_dict:
			i = edges_dict[i]
			if i == ori:
				return True
		return False
	edges_dict = {}
	get_father = {}
	for c in s:
		if len(edges_dict.keys()) == 26:
			break
		if ord(c) - ord('a') in get_father:
			continue
		for i in range(26):
			if i not in edges_dict and i != ord(c) - ord('a'):
				edges_dict[i] = ord(c) - ord('a')
				if not check(edges_dict, i):
					get_father[ord(c) - ord('a')] = i
					break
				else:
					del edges_dict[i]
	ans = []
	ss = 'abcdefghijklmnopqrstuvwxyz'
	for c in s:
		ans.append(ss[get_father[ord(c) - ord('a')]])
	return ''.join(ans)
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(getResult(n, s))


import math
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	d = {}
	gd = {}
	s = [-1 for k in range(26)]

	def find(i):
		while s[i] >= 0:
			i = s[i]
		return i

	def union(x, y):
		z = s[x] + s[y]
		if s[x] <= s[y]:
			s[x] = z
			s[y] = x
		else:
			s[x] = y
			s[y] = z
	res = ''
	for j in st:
		if j in gd:
			res += gd[j]
			continue
		for k in range(26):
			if k not in d:
				x = find(k)
				y = find(ord(j) - 97)
				if x != y or abs(s[x]) == 26:
					union(x, y)
					d[k] = 1
					gd[j] = chr(k + 97)
					res += gd[j]
					break
				else:
					continue
			else:
				continue
	print(res)


def firstinlist(letter):
	while letter in back:
		letter = back[letter]
	return letter
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	t = input()
	used = {}
	back = {}
	notavail = set()
	res = ''
	for l in t:
		if l in used:
			res += used[l]
		else:
			for testnumber in range(ord('a'), ord('z') + 1):
				if not testnumber in notavail:
					if len(used) == 25 or chr(testnumber) != firstinlist(l):
						used[l] = chr(testnumber)
						back[chr(testnumber)] = l
						notavail.add(testnumber)
						res += used[l]
						break
	print(res)


def work():
	input()
	s = input()
	nexts = [None] * 26
	prevs = [None] * 26

	def travel(cur):
		siz = 1
		while nexts[cur] != None:
			siz += 1
			cur = nexts[cur]
		return (cur, siz)
	for c in s:
		curval = ord(c) - 97
		if prevs[curval] != None:
			continue
		(v2, siz) = travel(curval)
		for plaintxt_cand in range(26):
			if plaintxt_cand == v2 and siz != 26:
				continue
			if nexts[plaintxt_cand] != None:
				continue
			prevs[curval] = plaintxt_cand
			nexts[plaintxt_cand] = curval
			break
	ans = ''.join([chr(prevs[ord(c) - 97] + 97) for c in s])
	print(ans)
tn = int(input())
for ti in range(tn):
	work()


import math
tc = int(input())
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def check_circle(k):
	start_node = k
	next_node = k
	while True:
		next_node = dec[next_node]
		if next_node == -1:
			return False
		if next_node == start_node:
			return True
for z in range(0, tc):
	l = int(input())
	s = input()
	anc = [-1] * 26
	dec = [-1] * 26
	string = ''
	edges = 0
	for i in range(0, l):
		letter = s[i]
		ind = ord(letter) - 97
		if dec[ind] == -1:
			for k in range(0, 26):
				if edges == 25:
					if anc[k] == -1:
						anc[k] = ind
						dec[ind] = k
						string += alphabet[k]
						edges += 1
				if anc[k] == -1 and k != ind:
					anc[k] = ind
					dec[ind] = k
					if not check_circle(k):
						string += alphabet[k]
						edges += 1
						break
					else:
						dec[ind] = -1
						anc[k] = -1
		else:
			string += alphabet[dec[ind]]
	print(string)


def helper(S, j):
	c = 0
	p = j
	while p != -1:
		c += 1
		p = S[p]
		if p == j:
			return c
	return -1
test = int(input())
for t in range(test):
	n = int(input())
	A = input()
	S = [-1] * 26
	ref = [1] * 26
	u = ord('a')
	for i in A:
		if S[ord(i) - u] == -1:
			for j in range(26):
				if ref[j] != 0 and j != ord(i) - u:
					S[ord(i) - u] = j
					a = helper(S, j)
					if a != -1 and a != 26:
						continue
					else:
						ref[j] = 0
						break
	Sa = ''
	for i in A:
		Sa += chr(S[ord(i) - u] + u)
	print(Sa)


def fnd(x, fa):
	if x != fa[x]:
		fa[x] = fnd(fa[x], fa)
	return fa[x]
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	e = []
	fa = []
	val = []
	st = []
	res = ''
	for i in range(26):
		fa.append(i)
		val.append(i)
		st.append(False)
		e.append(1)
	for i in s:
		ch = ord(i) - 97
		if val[ch] == ch:
			for j in range(26):
				if st[j]:
					continue
				pa = fnd(j, fa)
				pb = fnd(ch, fa)
				if pa != pb or e[pa] == 26:
					fa[pa] = pb
					e[pb] += e[pa]
					st[j] = True
					val[ch] = j
					break
			res += chr(val[ch] + 97)
		else:
			res += chr(val[ch] + 97)
	print(res)


tests = int(input())
for _ in range(tests):
	length = int(input())
	givenString = input()
	edge = [-1] * 26
	redge = [-1] * 26

	def getPathEnd(c):
		l = 0
		cur = c
		while edge[cur] != -1:
			l += 1
			cur = edge[cur]
		return (cur, l)
	vec = []
	for c in givenString:
		vec.append(ord(c) - ord('a'))
	for i in range(length):
		if edge[vec[i]] == -1:
			for c in range(26):
				if redge[c] == -1:
					(clast, len) = getPathEnd(c)
					if clast != vec[i] or len == 25:
						edge[vec[i]] = c
						redge[c] = vec[i]
						break
		vec[i] = edge[vec[i]]
	ans = ''
	for i in range(length):
		ans += chr(vec[i] + ord('a'))
	print(ans)


from collections import *
from math import *
from sys import *

def check(A, j):
	cnt = 0
	p = j
	while p != -1:
		cnt += 1
		p = A[p]
		if p == j:
			return cnt
	return -1
T = int(input())
for _ in range(T):
	N = int(input())
	A = input()
	B = [-1] * 26
	C = [1] * 26
	D = ''
	for i in range(N):
		if B[ord(A[i]) - 97] == -1:
			for j in range(26):
				if C[j] != 0 and j != ord(A[i]) - 97:
					B[ord(A[i]) - 97] = j
					z = check(B, j)
					if z != -1 and z != 26:
						continue
					else:
						C[j] = 0
						break
		D += chr(B[ord(A[i]) - 97] + 97)
	print(D)


def is_connected(cycle_map, start, end):
	target = start
	while 1:
		if not target in cycle_map:
			return False
		target = cycle_map[target]
		if target == end:
			return True
for _ in range(int(input())):
	input()
	s = list(map(ord, list(input())))
	cycle_map = {}
	t_map = {}
	ss = []
	[ss.append(x) for x in s if not x in ss]
	pointed = set()
	pointing = set()
	for c in ss:
		next = 97
		while 1:
			if c != next:
				if not next in pointed:
					if not is_connected(cycle_map, next, c):
						break
					if len(pointing) == 25:
						break
					if not c in pointed:
						break
			next += 1
		cycle_map[c] = next
		t_map[chr(c)] = chr(next)
		pointed.add(next)
		pointing.add(c)
	print(''.join([chr(cycle_map[c]) for c in s]))


import bisect
import heapq
from collections import defaultdict, deque
from email import header
from functools import lru_cache
from sys import stdin, stdout
import math
import sys
input = stdin.readline

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

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

def ss():
	x = stdin.readline()
	if x[-1] == '\n':
		return x[:-1]
	return x

def lss():
	return list(map(str, stdin.readline().split()))

def llss():
	return [i for i in ss()]

def yes():
	stdout.write('YES\n')

def no():
	stdout.write('NO\n')
for _ in range(ii()):
	n = ii()
	t = llss()
	inn = {}
	out = {}
	res = []
	asc = 'abcdefghijklmnopqrstuvwxyz'
	for i in asc:
		out[i] = False
		inn[i] = False
	cnt = 0

	def path(x):
		visited = set()
		while out[x] != False:
			if x in visited:
				return True
			visited.add(x)
			x = out[x]
		return False
	for i in t:
		if out[i] != False:
			res.append(out[i])
			continue
		for j in asc:
			if inn[j] == False and j != i:
				inn[j] = i
				out[i] = j
				if path(j):
					if cnt == 25:
						cnt += 1
						res.append(j)
						break
					else:
						inn[j] = False
						out[i] = False
				else:
					cnt += 1
					res.append(j)
					break
	print(''.join(res))


t = int(input())
for i in range(t):
	n = int(input())
	_str = input()
	_s = set(range(26))
	d1 = dict()
	for j in range(n):
		c = ord(_str[j]) - ord('a')
		if c in d1.keys():
			print(chr(d1[c] + ord('a')), end='')
			continue
		else:
			min_value = min(_s)
			temp = min_value
			while temp in d1.keys():
				temp = d1[temp]
			if c == temp and len(_s) != 1:
				d1[c] = min(_s - {min_value})
			else:
				d1[c] = min_value
		print(chr(d1[c] + ord('a')), end='')
		_s.remove(d1[c])
	print()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()
	l1 = [chr(i) for i in range(97, 123)]
	l2 = [None for i in range(26)]
	d = dict(zip(l1, l2))
	done = ''
	already = ''
	for i in range(n):
		if d[s[i]] == None:
			for j in l1:
				if j not in done and j != s[i] and (d[j] != s[i]):
					d[s[i]] = j
					k = s[i]
					loop = 0
					cp = 1
					while loop < 26:
						k = d[k]
						loop += 1
						if d[k] == s[i]:
							d[s[i]] = None
							cp = 0
							break
						elif d[k] == None:
							done += j
							break
					if loop == 25:
						d[s[i]] = j
						break
					if cp == 1:
						break
	ans = ''
	for i in range(n):
		ans += d[s[i]]
	print(ans)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	t = input()
	d = defaultdict(lambda : '')
	mp = defaultdict(lambda : False)
	ne = 0
	ref = 'abcdefghijklmnopqrstuvwxyz'
	ans = ''
	for x in t:
		if d[x]:
			ans += d[x]
		else:
			for ch in ref:
				if ch != x and (not mp[ch]):
					d[x] = ch
					ne += 1
					tmp = x
					for j in range(26):
						tmp = d[tmp]
						if not tmp:
							break
					if tmp == '' or ne == 26:
						mp[ch] = True
						ans += ch
						break
					else:
						d[x] = ''
						ne -= 1
	print(ans)


def solve():
	n = int(input())
	s = input()
	current_min = 'a'
	mapping = {}
	left_used = set()
	ans = []

	def next_of(x):
		if x == 'z':
			return 'a'
		return chr(ord(x) + 1)

	def connected(start, end):
		count = 0
		node = start
		while node in mapping and node != end:
			count += 1
			node = mapping[node]
		if count == 25:
			return False
		return node == end
	for i in s:
		if i in mapping:
			ans.append(mapping[i])
			continue
		temp_min = current_min
		while temp_min == i or temp_min in left_used or connected(temp_min, i):
			temp_min = next_of(temp_min)
		left_used.add(temp_min)
		mapping[i] = temp_min
		ans.append(temp_min)
	return ''.join(ans)
t = int(input())
while t:
	print(solve())
	t -= 1


N = int(input())

def p(dp, q, level=0):
	if level == 26:
		return (q, 26)
	if q not in dp:
		return (q, level)
	return p(dp, dp[q], level + 1)
for _ in range(N):
	dp = {}
	dp_r = {}
	Q = 'abcdefghijklmnopqrstuvwxyz'
	n = int(input())
	A = input().strip('\r\n')
	ans = []
	for v in A:
		if v in dp_r:
			ans.append(dp_r[v])
			continue
		for i in Q:
			if i not in dp and i != v:
				(P, D) = p(dp, v, 0)
				if P == i and D < 25:
					continue
				dp[i] = v
				dp_r[v] = i
				ans.append(dp_r[v])
				break
	print(''.join(ans))


alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

def opp(ar, j):
	c = 0
	p = j
	while p != -1:
		c += 1
		p = ar[p]
		if p == j:
			return c
	return -1
for _ in range(int(input())):
	n = int(input())
	s = input()
	ar = [-1] * 26
	ref = [1] * 26
	for i in range(n):
		b = alpha.index(s[i])
		if ar[b] == -1:
			for j in range(26):
				if ref[j] != 0 and j != b:
					ar[b] = j
					z = opp(ar, j)
					if z != -1 and z != 26:
						continue
					else:
						ref[j] = 0
						break
		print(str(alpha[ar[b]]), end='')
	print()


t = int(input())
results = []
alph = 'abcdefghijklmnopqrstuvwxyz'

def circle(sdvig: dict, letter, curr):
	sdvig[letter] = alph[curr]
	next = letter
	i = 0
	while i != 25:
		next = sdvig.get(next)
		if next == None:
			return False
		if next == letter:
			return True
		i += 1
	sdvig[letter] = None
	return False
for _ in range(t):
	res = ''
	used = set()
	n = int(input())
	s = input()
	sdvig = dict()
	for letter in s:
		if sdvig.get(letter) == None:
			curr = 0
			while letter == alph[curr] or alph[curr] in used or circle(sdvig, letter, curr):
				curr += 1
			sdvig[letter] = alph[curr]
			used.add(alph[curr])
			res = res + sdvig[letter]
		else:
			res = res + sdvig[letter]
	results.append(res)
list(map(print, results))


t = eval(input())

def f(x):
	if x not in k:
		return x
	else:
		return f(k[x])
for i in range(t):
	n = eval(input())
	s = input()
	k = {}
	a = 0
	k1 = [0] * 26
	ans = []
	p = 26
	for i in s:
		if i not in k:
			p -= 1
			for j in range(26):
				if k1[j] != 1 and i != chr(j + 97):
					if chr(j + 97) in k:
						if p == 0:
							k[i] = chr(j + 97)
							k1[j] = 1
							break
						if i != f(chr(j + 97)):
							k[i] = chr(j + 97)
							k1[j] = 1
							break
					else:
						k[i] = chr(j + 97)
						k1[j] = 1
						break
	for i in s:
		ans.append(k[i])
	for i in ans:
		print(i, end='')
	print()


for _ in range(int(input())):
	n = int(input())
	t = input()
	used = set()
	mapping = {}

	def has(l, c):
		while l in mapping:
			l = mapping[l]
			if l == c:
				return True
		return False
	for c in t:
		if c in mapping:
			continue
		for i in range(26):
			l = chr(i + ord('a'))
			if l in used or l == c or (l in mapping and has(l, c) and (len(mapping) < 25)):
				continue
			mapping[c] = l
			used.add(l)
			break
	print(''.join((mapping[c] for c in t)))


for _ in range(int(input())):
	n = int(input())
	a = [*input()]
	counter = 0
	alpha = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
	set1 = set()
	set2 = set()
	k = {}
	for i in a:
		if k.get(i, -1) == -1:
			al2 = alpha.copy()
			if i in al2:
				al2.remove(i)
			flag = True
			while flag == True:
				m = min(al2)
				count = 0
				z = m
				while count != 26 or z != i:
					if k.get(z, -1) == -1:
						flag = False
						break
					else:
						z = k[z]
						count += 1
						if count == 25:
							flag = False
							break
						if z == i:
							flag = True
							break
				if flag == True:
					al2.remove(m)
					m = min(al2)
			k[i] = m
			alpha.remove(m)
	for i in a:
		print(k[i], end='')
	print()


t = int(input())
for case in range(t):
	n = int(input())
	s = input()
	cyc = [-1] * 26
	rcyc = [-1] * 26
	count = 0
	out = []
	for c in s:
		v = ord(c) - 97
		if cyc[v] != -1:
			out.append(chr(97 + cyc[v]))
			continue
		bad = [False] * 26
		if count < 25:
			u = v
			while u != -1:
				bad[u] = True
				u = rcyc[u]
		count += 1
		for i in range(26):
			if rcyc[i] == -1 and (not bad[i]):
				cyc[v] = i
				rcyc[i] = v
				break
		out.append(chr(97 + cyc[v]))
	print(''.join(out))


def solve(arr, n):
	ctr = 0
	k = n
	while k != -1:
		ctr += 1
		k = arr[k]
		if k == n:
			return ctr
	return -1
for _ in range(int(input())):
	n = int(input())
	string = input()
	alpha = [-1 for i in range(26)]
	arr = [1 for i in range(26)]
	for i in range(n):
		if alpha[ord(string[i]) - ord('a')] == -1:
			for j in range(26):
				if arr[j] != 0 and j != ord(string[i]) - ord('a'):
					alpha[ord(string[i]) - ord('a')] = j
					bb = solve(alpha, j)
					if bb != -1 and bb != 26:
						continue
					else:
						arr[j] = 0
						break
		print(chr(alpha[ord(string[i]) - ord('a')] + ord('a')), end='')
	print()


def check(c):
	cnt = 0
	while c in mp:
		cnt += 1
		c = mp[c]
		if cnt > 26:
			return False
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	mp = {}
	used = set()
	res = ''
	for ch in s:
		if ch not in mp:
			if len(mp) == 25:
				for i in range(ord('a'), ord('z') + 1):
					c = chr(i)
					if c not in used:
						mp[ch] = c
						break
			else:
				for i in range(ord('a'), ord('z') + 1):
					c = chr(i)
					if c != ch and c not in used:
						mp[ch] = c
						if check(c):
							used.add(c)
							break
						else:
							mp.pop(ch)
		res += mp[ch]
	print(res)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	cir = [-1] * 26
	lis = [1] * 26
	for i in S:
		if cir[ord(i) - ord('a')] == -1:
			for j in range(26):
				if lis[j] != 0 and j != ord(i) - ord('a'):
					cir[ord(i) - ord('a')] = j
					count = 0
					temp = j
					flag = 1
					while temp != -1:
						count += 1
						temp = cir[temp]
						if temp == j:
							flag = 0
							break
					if flag:
						count = -1
					if count != -1 and count != -1:
						continue
					else:
						lis[j] = 0
						break
		print(chr(cir[ord(i) - ord('a')] + ord('a')), end='')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	seq = {}
	ispresent = {}
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	canwetake = {}
	for i in alpha:
		seq.setdefault(i, -1)
		ispresent.setdefault(i, -1)
		canwetake.setdefault(i, 1)
	count = 0
	ans = ''
	for i in range(n):
		if seq[s[i]] == -1:
			for j in alpha:
				if s[i] != j and ispresent[j] == -1:
					ref = j
					if count == 25:
						seq[s[i]] = j
						break
					isjpresent = -1
					while seq[ref] != -1:
						if s[i] == seq[ref]:
							isjpresent = 1
							break
						ref = seq[ref]
					if isjpresent != 1:
						seq[s[i]] = j
						count += 1
						ispresent[j] = 1
						break
		ans += seq[s[i]]
	print(ans)


import sys, threading

def main():

	def dfs(lttr, visited):
		(res, size) = (False, 0)
		if lttr in visited:
			return (True, len(visited))
		else:
			visited.add(lttr)
			if lttr in graph:
				(res, size) = res or dfs(graph[lttr], visited)
		return (res, size)
	t = int(input())
	for _ in range(t):
		n = int(input())
		word = input()
		graph = {}
		alphabet = [0] * 26
		for lttr in word:
			if lttr not in graph:
				for (i, is_taken) in enumerate(alphabet):
					candidate_chr = chr(ord('a') + i)
					if is_taken == 0 and candidate_chr != lttr:
						graph[lttr] = candidate_chr
						alphabet[i] = 1
						(cycle_created, size) = dfs(lttr, set())
						if cycle_created == True and size < 26:
							graph.pop(lttr)
							alphabet[i] = 0
						else:
							break
		ans = ''
		for lttr in word:
			ans += graph[lttr]
		print(ans)
threading.stack_size(1 << 27)
sys.setrecursionlimit(1 << 30)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


def cq(out, i):
	c = 1
	k = out[i]
	while 1 > 0:
		if k == -1 or k == i:
			break
		else:
			k = out[k]
			c += 1
	if c != 26 and k == i:
		return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	s = input()
	di = {}
	out = [-1] * 26
	s1 = ''
	for x in s:
		if x in di:
			s1 = s1 + di[x]
		else:
			for i in range(26):
				if i != ord(x) - 97 and out[i] == -1:
					out[i] = ord(x) - 97
					if cq(out, i) == 1:
						di[x] = chr(i + 97)
						s1 = s1 + di[x]
						break
					else:
						out[i] = -1
	print(s1)


for _ in range(int(input())):
	n = int(input())
	li = list(input())
	di = {}
	for i in range(26):
		di[chr(i + 97)] = '0'
	ans = ''
	se = set()
	for i in range(n):
		x = li[i]
		if di[x] != '0':
			ans += di[x]
			continue
		for j in range(26):
			bo = True
			y = chr(j + 97)
			if y in se:
				continue
			while y != '0':
				if y == x and len(se) < 25:
					bo = False
					break
				y = di[y]
			if bo:
				se.add(chr(j + 97))
				ans += chr(j + 97)
				di[x] = chr(j + 97)
				break
	print(ans)


import math
t = int(input())
chars = [chr(x) for x in range(97, 97 + 26)]
alp = [0] * 26
alpi = [0] * 26

def getNo(x):
	return ord(x) - 97

def checkCircle(x, y):
	cnt = 1
	init = y
	while x != 0 and cnt < 26:
		cnt += 1
		x = alp[getNo(x)]
		if y == x and cnt < 26:
			return False
	return True
for i in range(t):
	n = int(input())
	a = input()
	alp = [0] * 26
	alpi = [0] * 26
	res = ''
	for char in a:
		if alp[getNo(char)] != 0:
			res = res + alp[getNo(char)]
		else:
			for c in chars:
				if c != char and alpi[getNo(c)] == 0 and checkCircle(c, char):
					res = res + c
					alp[getNo(char)] = c
					alpi[getNo(c)] = char
					break
	print(res)


t = int(input())
for test in range(t):
	used = []
	vin = []
	vout = []
	for i in range(123):
		vin.append(0)
		vout.append(0)
	n = int(input())
	a = list(input())
	for c in range(n):
		x = a[c]
		if vout[ord(x)] != 0:
			continue
		for i in range(97, 123):
			if chr(i) == x:
				continue
			if vin[i] != 0:
				continue
			curr = i
			q = True
			cyclength = 1
			for j in range(30):
				if vout[curr] == x:
					if cyclength != 25:
						q = False
				if vout[curr] == 0:
					break
				curr = ord(vout[curr])
				cyclength += 1
			if q:
				vin[i] = x
				vout[ord(x)] = chr(i)
				break
	res = ''
	for c in range(n):
		res += vout[ord(a[c])]
	print(res)


for _ in range(int(input())):
	n = int(input())
	t = input()
	a = 'abcdefghijklmnopqrstuvwxyz'
	baap = {}
	beta = {}
	for i in range(n):
		if t[i] in beta:
			continue
		j = 0
		x = t[i]
		ct = 0
		while x in baap:
			x = baap[x]
			ct += 1
		while a[j] in baap or a[j] == t[i] or (x == a[j] and ct != 25):
			j = (j + 1) % 26
		beta[t[i]] = a[j]
		baap[a[j]] = t[i]
	for i in t:
		print(beta[i], end='')
	print()


from string import ascii_lowercase

def solve(n, s):
	not_used = list(ascii_lowercase)
	used = []
	new_s = ''
	for i in range(n):
		if s[i] in s[:i]:
			new_s += new_s[s.index(s[i])]
		else:
			if s[i] not in used:
				if s[i] != not_used[0]:
					new_s += not_used.pop(0)
				else:
					new_s += not_used.pop(1)
			else:
				k = 2
				x = s[new_s.index(s[i])]
				while x != not_used[0]:
					if x in used:
						x = s[new_s.index(x)]
					k += 1
					if k == 26:
						new_s += not_used.pop(0)
						break
				else:
					new_s += not_used.pop(1)
			used.append(new_s[-1])
	return new_s
t = int(input())
output = []
for i in range(t):
	n = int(input())
	s = input()
	output.append(solve(n, s))
for o in output:
	print(o)


t = int(input())
while t:
	mp = {}
	mem = {}
	a = 'abcdefghijklmnopqrstuvwxyz'
	val = 0
	for i in a:
		mp[i] = val
		val += 1
	parent = []
	for i in range(len(a)):
		parent.append(i)
	st = set()

	def getparent(val):
		if parent[val] == val:
			return val
		parent[val] = getparent(parent[val])
		return parent[val]

	def getval(char):
		if mem.get(char, '-') != '-':
			return mem[char]
		aparent = getparent(mp[char])
		for i in a:
			bparent = getparent(mp[i])
			if aparent != bparent and i not in st:
				st.add(i)
				parent[aparent] = bparent
				return i
		for i in a:
			if i not in st:
				st.add(i)
				return i
		return '-'
	t -= 1
	n = int(input())
	s = input()
	ans = ''
	for i in range(len(s)):
		mem[s[i]] = getval(s[i])
		ans += mem[s[i]]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	m = {}
	t = ''
	for c in s:
		if c not in m.keys():
			for i in range(26):
				x = chr(i + ord('a'))
				if x == c or x in m.values():
					continue
				while x in m.keys() and m[x] != c:
					x = m[x]
				if x not in m.keys():
					m[c] = chr(i + ord('a'))
					break
				if len(m) == 25:
					m[c] = chr(i + ord('a'))
					break
		t += m[c]
	print(t)


import sys
import math
line_num = 1
for line in sys.stdin:
	if line_num == 1 or line_num % 2 == 0:
		line_num += 1
		continue
	string = line.strip()
	next = [''] * 26
	prev = [''] * 26
	res = []
	for ch in string:
		index = ord(ch) - ord('a')
		if next[index] != '':
			res.append(next[index])
		else:
			dontChoose = set()
			ptr = index
			dontChoose.add(index)
			while prev[ptr] != '':
				dontChoose.add(ord(prev[ptr]) - 97)
				ptr = ord(prev[ptr]) - 97
			for elem in next:
				if elem != '':
					dontChoose.add(ord(elem) - 97)
			i = 0
			while i == index or i in dontChoose:
				i += 1
			if len(dontChoose) == 26:
				i = ptr
			res.append(chr(i + 97))
			next[index] = chr(i + 97)
			prev[i] = chr(index + 97)
	print(''.join(res))
	line_num += 1


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

class DisjointSet:

	def __init__(self, n):
		self.parent = [_ for _ in range(n + 1)]

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

	def merge(self, x, y):
		x_set = self.find(x)
		y_set = self.find(y)
		self.parent[x] = y_set

def f(x):
	return ord(x) - 97
for _ in range(int(input())):
	n = int(input())
	s = list(map(f, input()[:n]))
	DS = DisjointSet(26)
	c = {}
	for i in s:
		if i in c:
			continue
		for j in range(26):
			if i != j and DS.find(j) == j and (DS.find(i) != j):
				c[i] = j
				DS.merge(j, i)
				break
		else:
			p = 0
			for papa in range(26):
				if DS.find(papa) == papa:
					p = papa
					break
			c[i] = p
	for i in s:
		print(chr(c[i] + 97), end='')
	print()


pre = [-1 for i in range(0, 30)]
to = [-1 for i in range(0, 30)]

def check(si, t):
	if pre[t] != -1:
		return pre[t] == si
	if to[si] != -1:
		return to[si] == t
	tmp = si
	cnt = 0
	while pre[tmp] != -1:
		tmp = pre[tmp]
		cnt += 1
	if tmp == t and cnt != 25:
		return False
	to[si] = t
	pre[t] = si
	return True
t = int(input())
while t:
	t -= 1
	n = int(input())
	k = input()
	s = []
	for i in range(0, n):
		s.append(ord(k[i]) - ord('a'))
	for i in range(0, 30):
		pre[i] = to[i] = -1
	ans = []
	for i in range(0, n):
		for j in range(0, 26):
			if check(s[i], j):
				ans.append(chr(j + 97))
	for i in range(0, len(ans)):
		print(ans[i], end='')
	print()