Polycarp has a string $s$ consisting of lowercase Latin letters.

He encodes it using the following algorithm.

He goes through the letters of the string $s$ from left to right and for each letter Polycarp considers its number in the alphabet:

if the letter number is single-digit number (less than $10$), then just writes it out;

if the letter number is a two-digit number (greater than or equal to $10$), then it writes it out and adds the number 0 after.

For example, if the string $s$ is code, then Polycarp will encode this string as follows:

'c' — is the $3$-rd letter of the alphabet. Consequently, Polycarp adds 3 to the code (the code becomes equal to 3);

'o' — is the $15$-th letter of the alphabet. Consequently, Polycarp adds 15 to the code and also 0 (the code becomes 3150);

'd' — is the $4$-th letter of the alphabet. Consequently, Polycarp adds 4 to the code (the code becomes 31504);

'e' — is the $5$-th letter of the alphabet. Therefore, Polycarp adds 5 to the code (the code becomes 315045).

Thus, code of string code is 315045.

You are given a string $t$ resulting from encoding the string $s$. Your task is to decode it (get the original string $s$ by $t$).


-----Input-----

The first line of the input contains an integer $q$ ($1 \le q \le 10^4$) — the number of test cases in the input.

The descriptions of the test cases follow.

The first line of description of each test case contains one integer $n$ ($1 \le n \le 50$) — the length of the given code.

The second line of the description of each test case contains a string $t$ of length $n$ — the given code. It is guaranteed that there exists such a string of lowercase Latin letters, as a result of encoding which the string $t$ is obtained.


-----Output-----

For each test case output the required string $s$ — the string that gives string $t$ as the result of encoding. It is guaranteed that such a string always exists. It can be shown that such a string is always unique.


-----Examples-----

Input
9
6
315045
4
1100
7
1213121
6
120120
18
315045615018035190
7
1111110
7
1111100
5
11111
4
2606
Output
code
aj
abacaba
ll
codeforces
aaaak
aaaaj
aaaaa
zf


-----Note-----

The first test case is explained above.

In the second test case, the answer is aj. Indeed, the number of the letter a is equal to $1$, so 1 will be appended to the code. The number of the letter j is $10$, so 100 will be appended to the code. The resulting code is 1100.

There are no zeros in the third test case, which means that the numbers of all letters are less than $10$ and are encoded as one digit. The original string is abacaba.

In the fourth test case, the string $s$ is equal to ll. The letter l has the number $12$ and is encoded as 120. So ll is indeed 120120.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Greedy algorithms


Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = input()
	arr = arr.replace('100', 'j')
	arr = arr.replace('200', 't')
	arr = arr.replace('110', 'k')
	arr = arr.replace('120', 'l')
	arr = arr.replace('130', 'm')
	arr = arr.replace('140', 'n')
	arr = arr.replace('150', 'o')
	arr = arr.replace('160', 'p')
	arr = arr.replace('170', 'q')
	arr = arr.replace('180', 'r')
	arr = arr.replace('190', 's')
	arr = arr.replace('210', 'u')
	arr = arr.replace('220', 'v')
	arr = arr.replace('230', 'w')
	arr = arr.replace('240', 'x')
	arr = arr.replace('250', 'y')
	arr = arr.replace('260', 'z')
	arr = arr.replace('1', 'a')
	arr = arr.replace('2', 'b')
	arr = arr.replace('3', 'c')
	arr = arr.replace('4', 'd')
	arr = arr.replace('5', 'e')
	arr = arr.replace('6', 'f')
	arr = arr.replace('7', 'g')
	arr = arr.replace('8', 'h')
	arr = arr.replace('9', 'i')
	print(arr)


alphabets = 'abcdefghijklmnopqrstuvwxyz'
dictionary = {}
for i in alphabets:
	s = alphabets.index(i) + 1
	if s >= 10:
		dictionary[str(s) + str(0)] = i
	else:
		dictionary[str(s)] = i

def decoder(string, length, dictionary):
	word = ''
	l = length - 1
	while l >= 0:
		if string[l] == '0':
			temp = string[l - 2:l + 1]
			word += dictionary[temp]
			l -= 3
		else:
			temp = string[l]
			word += dictionary[temp]
			l -= 1
	return word[-1::-1]
cases = int(input())
for i in range(cases):
	length = int(input())
	string = input()
	print(decoder(string, length, dictionary))


import string

def decode(t):
	decode = t
	decode = decode.replace('200', 't')
	for i in range(10, 27):
		s = str(i) + '0'
		decode = decode.replace(s, chr(i + 96))
	for i in range(1, 11):
		decode = decode.replace(str(i), chr(i + 96))
	return decode
q = int(input())
inputs = []
for i in range(q):
	n = int(input())
	t = input()
	inputs.append(t)
for t in inputs:
	print(decode(t))


q = int(input())
m = {str(e): chr(ord('a') + e - 1) for e in range(1, 27)}

def decode(t):
	i = len(t) - 1
	ret = []
	while i >= 0:
		if t[i] == '0':
			ret.append(m[t[i - 2:i]])
			i -= 3
		else:
			ret.append(m[t[i]])
			i -= 1
	return ''.join(ret[::-1])
for _ in range(q):
	n = input().strip()
	t = input()
	print(decode(t))


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 encode(t, n):
	result = ''
	i = 0
	if len(t) == n:
		while i < n:
			t_int = int(t[i])
			if t_int <= 2 and i + 2 < n and (t[i + 2] == '0'):
				if i + 3 < n and t[i + 3] == '0':
					result += alphabet[t_int - 1]
					i += 1
					continue
				t_int = int(t[i] + t[i + 1])
				i += 2
			result += alphabet[t_int - 1]
			i += 1
	return result

def main():
	q = int(input())
	s = []
	if q < 1 or q > 10000:
		return
	for i in range(q):
		n = int(input())
		if n < 1 or n > 50:
			return
		t = input()
		s.append(encode(t, n))
	return s

def printArray(array):
	for item in array:
		print(item)
printArray(main())


def encode(t, n):
	result = ''
	i = 0
	while i < n:
		t_int = int(t[i])
		if t_int <= 2 and i + 2 < n and (t[i + 2] == '0'):
			if i + 3 < n and t[i + 3] == '0':
				result += chr(t_int + 96)
				i += 1
				continue
			t_int = int(t[i] + t[i + 1])
			i += 2
		result += chr(t_int + 96)
		i += 1
	return result

def main():
	q = int(input())
	s = []
	for _ in range(q):
		n = int(input())
		t = input()
		s.append(encode(t, n))
	return s

def printArray(array):
	for item in array:
		print(item)
printArray(main())


nombre = int(input())
while nombre < 1 or nombre > 10 ** 4:
	nombre = int(input())
liste = []
for k in range(nombre):
	longueur = int(input())
	while longueur < 1 or longueur > 50:
		longueur = int(input())
	chaine = input()
	while len(chaine) != longueur:
		ch = input()
	liste.append(chaine)
for ch in liste:
	if '00' not in ch:
		while '0' in ch:
			x = ch.index('0')
			n = int(ch[x - 2:x])
			ch = ch.replace(ch[x - 2:x + 1], chr(ord('a') + n - 1))
		for i in range(len(ch)):
			if ch[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:
				ch = ch.replace(ch[i], chr(ord('a') + int(ch[i]) - 1))
		print(ch)
	else:
		while '00' in ch:
			x1 = ch.index('00')
			if ch[x1 - 1] == '1':
				ch = ch.replace('100', 'j')
			elif ch[x1 - 1] == '2':
				ch = ch.replace('200', 't')
		while '0' in ch:
			x = ch.index('0')
			n = int(ch[x - 2:x])
			ch = ch.replace(ch[x - 2:x + 1], chr(ord('a') + n - 1))
		for i in range(len(ch)):
			if ch[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '9']:
				ch = ch.replace(ch[i], chr(ord('a') + int(ch[i]) - 1))
		print(ch)


import string

def solve():
	result = []
	t = int(input())
	num_to_letter = {i: char for (i, char) in enumerate(string.ascii_lowercase, 1)}
	for _ in range(t):
		n = int(input())
		A = list(map(int, input()))
		decode = []
		i = len(A) - 1
		while i >= 0:
			if A[i] == 0:
				num = A[i - 2] * 10 + A[i - 1]
				decode.append(num_to_letter[num])
				i -= 3
			else:
				decode.append(num_to_letter[A[i]])
				i -= 1
		decode.reverse()
		decode = ''.join(decode)
		result.append(decode)
	for r in result:
		print(r)
solve()


def solve():
	n = int(input())
	a = input()[::-1]
	q = ''
	alf = sorted('qwertyuiopasdfghjklzxcvbnm')
	i = 0
	while i < n:
		if a[i] == '0':
			q += alf[int(a[i + 2] + a[i + 1]) - 1]
			i += 3
		else:
			q += alf[int(a[i]) - 1]
			i += 1
	return q[::-1]
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


def solve2(a):
	c = ''
	I = len(a) - 1
	while I >= 0:
		if a[I] == '0':
			b = 96 + int(a[I - 2:I])
			c += chr(b)
			I -= 3
		else:
			j = 96 + int(a[I])
			c += chr(j)
			I -= 1
	return c[::-1]

def solve():
	cases = int(input().rstrip())
	inp = []
	for i in range(cases):
		_ = input().rstrip()
		inp.append(input().rstrip())
	for I in range(cases):
		print(solve2(inp[I]))
solve()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	t = input().strip()
	ans = []
	idx = n - 1
	while idx >= 0:
		if t[idx] == '0':
			ans.append(chr(96 + int(t[idx - 2:idx])))
			idx -= 3
		else:
			ans.append(chr(96 + int(t[idx])))
			idx -= 1
	return ''.join(ans[::-1])
for _ in range(int(input())):
	print(solve())


from string import ascii_lowercase
lett = {str(index): letter for (index, letter) in enumerate(ascii_lowercase, start=1)}
t = int(input())
ans = [''] * t
for i in range(t):
	n = int(input())
	s = input()
	j = n - 1
	while j >= 0:
		if s[j] == '0':
			ans[i] = lett[s[j - 2:j]] + ans[i]
			j = j - 2
		else:
			ans[i] = lett[s[j]] + ans[i]
		j = j - 1
for i in range(t):
	print(ans[i], end='\n')


from itertools import count
from string import ascii_lowercase
letter_mapping = dict(list(map(lambda x: (str(x[0]), x[1]), zip(count(1), ascii_lowercase))))

def sol(s):
	i = len(s) - 1
	res = []
	while i >= 0:
		if s[i] == '0':
			res.append(letter_mapping.get(s[i - 2:i]))
			i -= 3
		else:
			res.append(letter_mapping.get(s[i]))
			i -= 1
	res.reverse()
	print(''.join(res))
t = int(input().strip())
for i in range(t):
	l = int(input().strip())
	s = input().strip()
	sol(s)


def main():
	letters = ['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']
	tests = int(input())
	while tests > 0:
		input()
		encoded = input()[::-1]
		reverse_decoded_string = ''
		char_count_after_zero = 0
		after_zero_number = 0
		analising_zero = False
		for code in encoded:
			code = int(code)
			if not analising_zero:
				if code == 0:
					analising_zero = True
					continue
				else:
					reverse_decoded_string += letters[code - 1]
			else:
				char_count_after_zero += 1
				if char_count_after_zero == 1:
					after_zero_number = code
					continue
				else:
					after_zero_number = code * 10 + after_zero_number
					reverse_decoded_string += letters[after_zero_number - 1]
					char_count_after_zero = 0
					after_zero_number = 0
					analising_zero = False
		reverse_decoded_string = reverse_decoded_string[::-1]
		print(reverse_decoded_string)
		tests -= 1
main()


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	code = input()
	alphabets = {'1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
	ans = ''
	index = length - 1
	while index >= 0:
		if code[index] == '0':
			ans = alphabets[code[index - 2:index]] + ans
			index = index - 3
		else:
			ans = alphabets[code[index]] + ans
			index = index - 1
	print(ans)


def solve():
	input()
	alphabet = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g', 8: 'h', 9: 'i', 98: 'j', 11: 'k', 12: 'l', 13: 'm', 14: 'n', 15: 'o', 16: 'p', 17: 'q', 18: 'r', 19: 's', 97: 't', 21: 'u', 22: 'v', 23: 'w', 24: 'x', 25: 'y', 26: 'z'}
	ans = []
	s = input()
	s = s.replace('100', '980').replace('200', '970')
	s = s[::-1]
	ts = ''
	c = 0
	for i in s:
		if i == '0':
			c = 1
			continue
		elif c >= 1 and c <= 2:
			ts += i
			if c == 2:
				ans.append(alphabet[int(ts[::-1])])
				c = 0
				ts = ''
			else:
				c += 1
		else:
			ans.append(alphabet[int(i)])
	print(''.join(ans[::-1]))
tc = int(input())
for t in range(tc):
	solve()


def decodestring(s, n, d):
	ans = ''
	i = n - 1
	while i > -1:
		if s[i] == '0':
			j = i - 2
			x = int(s[j]) * 10 + int(s[i - 1])
			ans += d[x]
			i -= 3
		else:
			ans += d[int(s[i])]
			i -= 1
	li = list(ans)
	li.reverse()
	print(''.join(li))
t = int(input())
li = 'abcdefghijklmnopqrstuvwxyz'
lt = list(li)
d = {}
for i in range(len(lt)):
	d[i + 1] = lt[i]
for i in range(t):
	n = int(input())
	s = input()
	decodestring(s, n, d)


def solve():
	n = int(input())
	s = input()
	i = len(s) - 1
	ans = ''
	while i >= 0:
		if s[i] != '0':
			ans += chr(ord(s[i]) - ord('0') + 96)
		else:
			t = s[i - 2] + s[i - 1]
			t = int(t) + 96
			t = chr(t)
			ans += t
			i -= 2
		i -= 1
	ans = ans[::-1]
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


for s in [*open(0)][2::2]:
	s = [*s[:-1]]
	r = ''
	while s:
		if (x := s.pop()) < '1':
			x = s[-2] + s[-1]
			s[-2:] = []
		r = chr(96 + int(x)) + r
	print(r)


charMap = {}
count = 1
for i in 'abcdefghijklmnopqrstuvwxyz':
	charMap[str(count)] = i
	count += 1
for _ in range(int(input())):
	l = int(input())
	numbers = [i for i in input()]
	s = ''
	i = l - 1
	while i >= 0:
		if numbers[i] == '0':
			s = charMap[numbers[i - 2] + numbers[i - 1]] + s
			i -= 3
		else:
			s = charMap[numbers[i]] + s
			i -= 1
	print(s)


t = int(input())
charArray = [chr(x + 97) for x in range(0, 26)]
lres = []
for _ in range(t):
	n = int(input())
	s = input()
	res = []
	i = n - 1
	while i >= 0:
		if s[i] != '0':
			res.append(charArray[int(s[i]) - 1])
			i -= 1
		else:
			res.append(charArray[int(s[i - 2]) * 10 + int(s[i - 1]) - 1])
			i -= 3
	lres.append(''.join(list(reversed(res))))
for i in lres:
	print(i)


test = int(input())
alpha = {'1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
for t in range(test):
	len_string = int(input())
	string = input()
	wordstring = ''
	i = len_string - 1
	while i >= 0:
		if string[i] == '0':
			bigstring = string[i - 2] + string[i - 1]
			wordstring = alpha[bigstring] + wordstring
			i -= 3
		else:
			wordstring = alpha[string[i]] + wordstring
			i -= 1
	print(wordstring)


def encode(t, n):
	result = ''
	i = n - 1
	while i >= 0:
		if t[i] == '0':
			result = chr(int(t[i - 2] + t[i - 1]) + 96) + result
			i -= 3
		else:
			result = chr(int(t[i]) + 96) + result
			i -= 1
	return result

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		t = input()
		print(encode(t, n))
main()


for s in [*map(int, open(0))][2::2]:
	r = ''
	while s:
		x = s % 10
		s //= 10
		if x < 1:
			x = s % 100
			s //= 100
		r = chr(96 + x) + r
	print(r)


def func():
	n = int(input())
	code = input()
	og_str = [''] * n
	acu = n - 1
	while acu > -1:
		if code[acu] != '0':
			a = chr(int(code[acu]) + 96)
			og_str[acu] = a
			acu -= 1
		else:
			a = code[acu - 2:acu]
			a = chr(int(a) + 96)
			og_str[acu] = a
			acu -= 3
	print(''.join(og_str))
	return
t = int(input())
for i in range(t):
	func()


def decode_str(t='210019013015120'):
	answer = ''
	i = len(t) - 1
	while i >= 0:
		if t[i] == '0':
			answer = chr(int(t[i - 2:i]) + 96) + answer
			i = i - 3
		else:
			answer = chr(int(t[i]) + 96) + answer
			i -= 1
	print(answer)
l = int(input())
s = []
for i in range(l):
	k = input()
	s.append(input())
for i in s:
	decode_str(i)


for X in [*map(int, open(0))][2::2]:
	F = ''
	while X:
		A = X % 10
		X //= 10
		if A < 1:
			A = X % 100
			X //= 100
		F = chr(96 + A) + F
	print(F)


for s in [*open(0)][2::2]:
	s = int(s[:-1])
	ans = ''
	while s:
		x = s % 10
		s //= 10
		if x < 1:
			x = s % 100
			s //= 100
		ans = chr(x + 96) + ans
	print(ans)


d = {}
for i in range(97, 123):
	d[str(i - 96)] = chr(i)
q = int(input())
while q:
	n = int(input())
	t = input()
	s = ''
	i = n - 1
	while i >= 0:
		if t[i] != '0':
			s += d[t[i]]
		else:
			x = t[i - 2] + t[i - 1]
			s += d[x]
			i -= 2
		i -= 1
	print(s[::-1])
	q -= 1


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	code = input()
	net = 'abcdefghijklmnopqrstuvwxyz'
	stack = []
	for i in range(n):
		c = code[i]
		if c != '0':
			stack.append(c)
		elif c == '0' and i + 1 < n and (code[i + 1] == '0'):
			stack.append(c)
		elif c == '0':
			x = stack.pop()
			y = stack.pop()
			num = y + x
			stack.append(num)
	ans = ''
	for i in stack:
		ind = int(i)
		ans += net[ind - 1]
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
from string import ascii_lowercase
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def Solve():
	min_ = 1
	max_ = len(ascii_lowercase)
	for t in range(int(input())):
		n = int(input())
		s = input().strip() + 'm'
		digits = []
		last_0 = 0
		for i in range(n):
			if s[i] == '0' and s[i + 1] != '0':
				digits.extend(list(s[last_0:i - 2]))
				digits.append(s[i - 2:i])
				last_0 = i
		else:
			digits.extend(list(s[last_0 + (last_0 != 0):]))
		digits = list(filter(lambda x: x != 'm' and x != '0', digits))
		new_s = ''
		for i in digits:
			new_s += ascii_lowercase[int(i) - 1]
		print(new_s)
Solve()


def main():
	n = int(input())
	numsstr = list(input())
	nums = list(map(int, numsstr))
	output = ''
	i = len(nums) - 1
	while i >= 0:
		if nums[i] == 0:
			output += chr(int(numsstr[i - 2] + numsstr[i - 1]) + 96)
			i -= 3
		else:
			output += chr(nums[i] + 96)
			i -= 1
	output = ''.join(list(reversed(list(output))))
	print(output)
t = int(input())
for i in range(t):
	main()


def main():
	for _ in range(int(input())):
		j = int(input())
		t = input()
		(res, i) = ('', j - 1)
		while i >= 0:
			if t[i] != '0':
				res += chr(int(t[i]) + 96)
				i = i - 1
			else:
				res += chr(int(t[i - 2:i]) + 96)
				i = i - 3
		print(res[::-1])
main()


def main():
	for _ in range(int(input())):
		m = int(input())
		n = input()
		(result, l) = ('', m - 1)
		while l >= 0:
			if n[l] != '0':
				result = chr(int(n[l]) + 96) + result
				l -= 1
			else:
				result = chr(int(n[l - 2:l]) + 96) + result
				l -= 3
		print(result)
main()


def solve(l):
	r = ''
	try:
		for i in range(n):
			t = l.pop()
			if t == '0':
				t1 = l.pop()
				t2 = l.pop()
				r += chr(int(t2 + t1) + 32 + 64)
			else:
				r += chr(int(t) + 32 + 64)
	except:
		return r[::-1]
	return r[::-1]
for _ in range(int(input())):
	n = int(input())
	l = [i for i in input()]
	print(solve(l))


def solve(s):
	string = ''
	i = len(s) - 1
	while i >= 0:
		if s[i] == '0' and i - 2 > -1:
			temp = int(s[i - 2] + s[i - 1])
			string += chr(temp + 96)
			i -= 3
		else:
			temp = int(s[i])
			string += chr(temp + 96)
			i -= 1
	print(string[::-1])
test = int(input())
while test:
	n = int(input())
	s = input()
	solve(s)
	test -= 1


N = ord('a')
for _ in range(int(input())):
	n = int(input())
	s1 = ''
	s = int(input())
	while s > 0:
		(s, r) = divmod(s, 10)
		if r == 0:
			(s, r) = divmod(s, 100)
		s1 += chr(N + r - 1)
	print(s1[::-1])


q = int(input())
result = []
alphabets = [chr(i + 97) for i in range(26)]
for i in range(q):
	n = int(input())
	code = input()
	j = n - 1
	ch = ''
	while j >= 0:
		if code[j] != '0':
			ch += alphabets[int(code[j]) - 1]
			j -= 1
		else:
			ch += alphabets[int(code[j - 2:j]) - 1]
			j -= 3
	result.append(ch[::-1])
for i in result:
	print(i)


import sys
sys.setrecursionlimit(10 ** 6)
from collections import Counter, deque, defaultdict
import math
import heapq
ip = sys.stdin.readline
op = sys.stdout.write
t = int(ip())
res = []
for _ in range(t):
	n = int(ip())
	s = ip()
	decoded_st = ''
	i = n - 1
	while i >= 0:
		if s[i] != '0':
			decoded_st += chr(int(s[i]) + 96)
			i -= 1
		else:
			c = s[i - 2] + s[i - 1]
			decoded_st += chr(int(c) + 96)
			i -= 3
	lst = list(decoded_st[::-1])
	res.append(''.join(lst))
for val in res:
	op(val + '\n')


import sys
import math
from functools import cmp_to_key
sys.setrecursionlimit(10 ** 9)

def solve():
	for t in range(int(input())):
		n = int(input())
		s = input()
		i = len(s) - 1
		result = ''
		while i >= 0:
			x = None
			if s[i] == '0':
				x = 96 + int(s[i - 2:i])
				i -= 3
			else:
				x = 96 + int(s[i])
				i -= 1
			result = chr(x) + result
		print(result)
solve()


def solve(s, n):
	ans = []
	i = 0
	while i < n:
		if i + 2 >= n:
			ans.append(chr(int(s[i]) + 96))
			i += 1
		elif s[i + 2] != '0' or (i + 3 < n and s[i + 2] == '0' and (s[i + 3] == '0')):
			ans.append(chr(int(s[i]) + 96))
			i += 1
		else:
			temp = 10 * int(s[i]) + int(s[i + 1])
			ans.append(chr(temp + 96))
			i += 3
	return ''.join(ans)
t = int(input())
for j in range(t):
	n = int(input())
	abc = input()
	ans = solve(abc, n)
	print(ans)


def solve():
	n = input()
	s = input()
	ans = ''
	i = len(s) - 1
	while i >= 0:
		if s[i] == '0':
			ans += chr(97 + int(s[i - 2] + s[i - 1]) - 1)
			i -= 3
		else:
			ans += chr(97 + int(s[i]) - 1)
			i -= 1
	print(ans[::-1])
t = int(input())
for _ in range(t):
	solve()


list_char = [chr(i) for i in range(97, 123)]
list_num1 = [str(i) for i in range(1, 10)]
list_num1 += [str(i) + '0' for i in range(10, 27)]
res = {list_num1[i]: list_char[i] for i in range(len(list_char))}
t = int(input())
for i in range(t):
	str2 = ''
	n = int(input())
	x = input()
	y = list(reversed(x))
	i = 0
	while i < len(y):
		if y[i] == '0':
			str2 += res[y[i + 2] + y[i + 1] + y[i]]
			i += 3
		else:
			str2 += res[y[i]]
			i += 1
	print(str2[::-1])


def exe():
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	i = n - 1
	ans = ''
	while i > -1:
		if s[i] == '0':
			ans += alpha[int(s[i - 2] + s[i - 1]) - 1]
			i -= 3
		else:
			ans += alpha[int(s[i]) - 1]
			i -= 1
	return ans[::-1]
for i in range(int(input())):
	n = int(input())
	s = input()
	print(exe())


total = int(input())
trans_list = '*ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for i in range(total):
	input()
	text = input()
	text = text.replace('200', trans_list[20])
	text = text.replace('100', trans_list[10])
	i = 26
	while True:
		if i == 0:
			break
		i_num = i
		if i > 9:
			i_num *= 10
		i_text = str(i_num)
		text = text.replace(i_text, trans_list[i])
		i -= 1
	print(text.lower())


import sys
import math
from collections import Counter

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

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

def fun(a):
	i = len(a) - 1
	arr = []
	while i >= 0:
		ans = ''
		if a[i] == '0':
			ans += a[i - 1]
			ans += a[i - 2]
			arr.append(ans[::-1])
			i -= 2
		else:
			arr.append(a[i])
		i -= 1
	arr = arr[::-1]
	ret = ''
	for i in arr:
		ret += chr(int(i) + 96)
	return ret
for _ in range(int(input())):
	b = input()
	a = input()
	print(fun(a))


a = ['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']
d = {}
for i in range(len(a)):
	d[str(i + 1)] = a[i]
q = int(input())
for i in range(q):
	n = int(input())
	t = input()
	word = ''
	t = t[::-1]
	j = 0
	while j < len(t):
		if t[j] == '0':
			word += d[t[j + 2:j:-1]]
			j += 3
		else:
			word += d[t[j]]
			j += 1
	print(word[::-1])


class Solution:

	def decode(self, s):
		decode_dict = {str(ord(i) - 96): i for i in 'abcdefghijklmnopqrstuvwxyz'}
		res = ''
		decode_dict['0'] = ''
		if len(s) <= 2:
			for i in range(len(s)):
				res += decode_dict[s[i]]
			return res
		skip = False
		for i in range(len(s) - 3):
			if skip:
				skip = False
				continue
			if s[i] == '0':
				continue
			if s[i + 2] == '0' and s[i + 3] != '0':
				res += decode_dict[s[i] + s[i + 1]]
				skip = True
			else:
				res += decode_dict[s[i]]
		if s[-1] == '0':
			res += decode_dict[s[-3] + s[-2]]
		elif skip:
			res += decode_dict[s[-1]]
		else:
			res += decode_dict[s[-3]] + decode_dict[s[-2]] + decode_dict[s[-1]]
		return res
ob = Solution()
q = int(input())
while q:
	n = int(input())
	s = input().strip()
	print(ob.decode(s))
	q -= 1


def solve():
	n = int(input())
	s = input()
	ord_a = 96
	i = n - 1
	result = ''
	while i >= 0:
		ord_val = int(s[i])
		if s[i] == '0':
			i -= 1
			ord_val = int(s[i - 1] + s[i])
			i -= 1
		alpha = chr(ord_val + ord_a)
		result = alpha + result
		i -= 1
	print(result)
t = int(input())
for _ in range(t):
	solve()


diction = [(1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), (5, 'e'), (6, 'f'), (7, 'g'), (8, 'h'), (9, 'i'), (10, 'j'), (11, 'k'), (12, 'l'), (13, 'm'), (14, 'n'), (15, 'o'), (16, 'p'), (17, 'q'), (18, 'r'), (19, 's'), (20, 't'), (21, 'u'), (22, 'v'), (23, 'w'), (24, 'x'), (25, 'y'), (26, 'z')]

def decoder(string, diction, length):
	i = 0
	decoded = ''
	while i < length:
		a = string[length - i - 1]
		if a == '0':
			b = string[length - i - 2]
			c = string[length - i - 3]
			cb = c + b
			bc = diction[int(cb) - 1][1]
			decoded = bc + decoded
			i += 3
		else:
			decoded = diction[int(a) - 1][1] + decoded
			i += 1
	return decoded
t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	print(decoder(string, diction, n))


def main():
	for _ in range(int(input())):
		q = int(input())
		w = input()
		(res, e) = ('', q - 1)
		while e >= 0:
			if w[e] != '0':
				res = chr(int(w[e]) + 96) + res
				e -= 1
			else:
				res = chr(int(w[e - 2:e]) + 96) + res
				e -= 3
		print(res)
main()


from collections import defaultdict
st = 'abcdefghijklmnopqrstuvwxyz'
num = 1
d = defaultdict(lambda : -1)
for i in st:
	d[str(num)] = i
	num += 1
n = int(input())
for _ in range(n):
	nu = int(input())
	st = str(input())
	st = st[::-1]
	i = 0
	an = ''
	while i < nu:
		if st[i] == '0':
			val = st[i + 1] + st[i + 2]
			val = val[::-1]
			an += d[val]
			i += 2
		else:
			an += d[st[i]]
		i += 1
	print(an[::-1])


def decodeStr(code, sz):
	ltrCode = ''
	res = ''
	sz -= 1
	while sz > -1:
		if code[sz] == '0':
			ltrCode = code[sz - 2:sz]
			sz -= 3
		else:
			ltrCode = code[sz]
			sz -= 1
		res = chr(ord('a') + int(ltrCode) - 1) + res
		ltrCode = ''
	return res
t = int(input())
while t:
	length = int(input())
	myStr = input()
	print(decodeStr(myStr, length))
	t -= 1


t = int(input())
alph = ['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']
ans = []
for _ in range(t):
	a = ''
	n = int(input())
	t = input()
	i = n - 1
	while i >= 0:
		if t[i] == '0':
			a = alph[int(t[i - 2:i]) - 1] + a
			i -= 3
		else:
			a = alph[int(t[i]) - 1] + a
			i -= 1
	ans.append(a)
for i in ans:
	print(i)


def Favaku():
	for Z in range(int(input())):
		a = int(input())
		b = input()
		(res, i) = ('', a - 1)
		while i >= 0:
			if b[i] != '0':
				res = chr(int(b[i]) + 96) + res
				i -= 1
			else:
				res = chr(int(b[i - 2:i]) + 96) + res
				i -= 3
		print(res)
Favaku()


def decode(n, s):
	res = ''
	if n < 3:
		for i in range(n):
			res += chr(96 + int(s[i]))
		return res
	i = 0
	while i < n:
		if i + 3 < n and (s[i + 2] == '0' and s[i + 3] != '0'):
			res += chr(96 + int(s[i:i + 2]))
			i += 3
		elif n - i == 3 and s[i + 2] == '0':
			res += chr(96 + int(s[i:i + 2]))
			i += 3
		else:
			res += chr(96 + int(s[i]))
			i += 1
	return res
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(decode(n, s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {'0': '', '1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
	st = ''
	i = len(s) - 1
	while i >= 0:
		if s[i] == '0':
			st += d[s[i - 2] + s[i - 1]]
			i -= 3
		elif s[i] != '0':
			st += d[s[i]]
			i -= 1
	print(st[::-1])


def decode():
	n = int(input())
	for _ in range(n):
		m = int(input())
		dupes = input()
		res = ''
		(start, end) = (0, len(str(dupes)) - 1)
		for i in range(len(dupes) - 1, -1, -1):
			while start <= end:
				if dupes[end] != '0':
					val = int(dupes[end]) + 96
					res += chr(val)
				elif dupes[end] == '0':
					val = 96 + int(dupes[end - 2] + dupes[end - 1])
					end -= 2
					res += chr(val)
				end -= 1
		print(res[::-1])
decode()


def runner(n):
	res = []
	i = len(n) - 1
	while i >= 0:
		if n[i] != '0':
			res.append(n[i])
			i -= 1
		else:
			s = i - 2
			res.append(n[s:i])
			i -= 3
	ss = ''
	for i in res:
		ss += chr(int(i) + 97 - 1)
	return ss[::-1]
b = int(input())
for i in range(b):
	a = int(input())
	n = str(input())
	print(runner(n))


def solve():
	n = int(input())
	s = input()
	s1 = ''
	while n != 0:
		if s[n - 1] == '0':
			num = s[n - 3] + s[n - 2]
			num1 = int(num) + 97
			s1 += chr(num1 - 1)
			n -= 3
		else:
			num = s[n - 1]
			num1 = int(num) + 97
			n -= 1
			s1 += chr(num1 - 1)
	print(s1[::-1])
for t in range(int(input())):
	solve()


def main():
	tc = int(input())
	for i in range(tc):
		n = int(input())
		code = input()
		print(decode(n - 1, code))

def decode(n, code):
	dict = {'1': 'a', '2': 'b', '3': 'c', '4': 'd', '5': 'e', '6': 'f', '7': 'g', '8': 'h', '9': 'i', '10': 'j', '11': 'k', '12': 'l', '13': 'm', '14': 'n', '15': 'o', '16': 'p', '17': 'q', '18': 'r', '19': 's', '20': 't', '21': 'u', '22': 'v', '23': 'w', '24': 'x', '25': 'y', '26': 'z'}
	temp = ''
	count = 0
	result = ''
	for i in range(n, -1, -1):
		if code[i] == '0':
			temp += code[i]
			count += 1
		elif '0' in temp and count < 3:
			temp += code[i]
			count += 1
			if count == 3:
				reverse = temp[::-1]
				result += dict[reverse[0:2]]
				count = 0
				temp = ''
		else:
			temp += code[i]
			reverse = temp[::-1]
			result += dict[reverse[0:2]]
			temp = ''
	return result[::-1]
main()


q = int(input())
for _ in range(q):
	n = int(input())
	code = list(map(int, list(input())))
	letters = []
	while code:
		cVal = code.pop()
		if not cVal:
			cVal = code.pop() + code.pop() * 10
		letters.append(chr(cVal + 96))
	letters.reverse()
	print(''.join(letters))


def solution(n, string):
	ans = []
	i = n - 1
	while i >= 0:
		if string[i] == '0' and i - 2 >= 0:
			cur = chr(ord('a') + int(string[i - 2:i]) - 1)
			i -= 3
		else:
			cur = chr(ord('a') + int(string[i]) - 1)
			i -= 1
		ans.append(cur)
	return ''.join(ans[::-1])
t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	print(solution(n, string))


import string

def decode(n, s):
	alph = string.ascii_lowercase
	res = ''
	c = n - 1
	while c != -1:
		if s[c] == '0':
			res += alph[int(s[c - 2:c + 1]) // 10 - 1]
			c -= 3
		else:
			res += alph[int(s[c]) - 1]
			c -= 1
	print(''.join(reversed(res)))
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	decode(n, s)


t = int(input())
d = {}
h = 0
for i in 'abcdefghijklmnopqrstuvwxyz':
	h += 1
	d[h] = i
for j in range(0, t):
	n = int(input())
	p = input()
	l = ''
	i = n - 1
	while i >= 0:
		if p[i] == '0':
			l = d[int(p[i - 2] + p[i - 1])] + l
			i -= 3
		else:
			l = d[int(p[i])] + l
			i -= 1
	print(l)


for _ in range(int(input())):
	n = int(input())
	s = input()
	p = list(s)
	a = 'abcdefghijklmnopqrstuvwxyz'
	l = list(a)
	i = n - 1
	g = []
	while i >= 0:
		d = int(p[i])
		if d != 0:
			g.append(l[d - 1])
			i = i - 1
		else:
			m = p[i - 2:i]
			o = ''.join(m)
			x = int(o)
			g.append(l[x - 1])
			i = i - 3
	print(''.join(reversed(g)))


alphabets = ['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']
t = int(input())
while t > 0:
	length = int(input())
	str = input()
	ans = ''
	i = length - 1
	while i >= 0:
		if str[i] != '0':
			ans += alphabets[int(str[i]) - 1]
		else:
			temp = str[i - 2] + str[i - 1]
			temp = int(temp)
			ans += alphabets[temp - 1]
			i -= 2
		i -= 1
	ans = ans[::-1]
	print(ans)
	t -= 1


qqq = 'abcdefghijklmnopqrstuvwxyz'
d = {}
c = 1
for i in qqq:
	d[str(c)] = i
	c = c + 1
q = int(input())
while q > 0:
	q = q - 1
	n = int(input())
	t = input()
	s = ''
	i = n - 1
	while i >= 0:
		if t[i] != '0':
			s = s + d[str(t[i])]
			i = i - 1
			continue
		s = s + d[str(t[i - 2]) + str(t[i - 1])]
		i = i - 3
	print(s[::-1])


for _ in range(int(input())):
	n = int(input())
	t = list(map(int, input()))
	answer = ''
	while t:
		x = t.pop()
		if not x:
			answer += chr(t.pop() + t.pop() * 10 + 96)
		else:
			answer += chr(x + 96)
	print(answer[::-1])


for q in range(int(input())):
	n = int(input())
	t = input()
	L = [int(c) for c in t]
	s = ''
	if t.count('0') == 0:
		for c in L:
			s = s + chr(c + ord('a') - 1)
	else:
		s = ''
		i = len(L) - 1
		while i >= 0:
			if L[i] != 0:
				s = chr(L[i] + ord('a') - 1) + s
				i = i - 1
			else:
				s1 = L[i - 2] * 10 + L[i - 1]
				c1 = chr(s1 + ord('a') - 1)
				s = c1 + s
				i = i - 3
	print(s)


for _ in range(int(input())):
	l = int(input())
	s = input()[::-1]
	d_code = ''
	i = 0
	while i < l:
		if s[i] == '0':
			d_code = chr(int(s[i + 2:i:-1]) + 96) + d_code
			i += 3
		else:
			d_code = chr(int(s[i]) + 96) + d_code
			i += 1
	print(d_code)


def decode(list_):
	i = 0
	final_string = ''
	while i < list_[0]:
		if i <= list_[0] - 3:
			if list_[1][i + 2] == '0':
				try:
					if list_[1][i + 3] == '0':
						final_string = final_string + chr(97 + int(list_[1][i]) - 1)
						i = i + 1
					else:
						final_string = final_string + chr(97 + int(list_[1][i:i + 2]) - 1)
						i = i + 3
				except:
					final_string = final_string + chr(97 + int(list_[1][i:i + 2]) - 1)
					i = i + 3
			else:
				final_string = final_string + chr(97 + int(list_[1][i]) - 1)
				i = i + 1
		else:
			final_string = final_string + chr(97 + int(list_[1][i]) - 1)
			i = i + 1
	return final_string
count_tot = int(input())
list_of_list = []
for i in range(count_tot):
	interim_list = []
	interim_list.append(int(input()))
	interim_list.append(input())
	list_of_list.append(interim_list)
for i in list_of_list:
	print(decode(i))