You are given a string $s$ of lowercase Latin letters.

The following operation can be used:

select one character (from 'a' to 'z') that occurs at least once in the string. And replace all such characters in the string with the previous one in alphabetical order on the loop. For example, replace all 'c' with 'b' or replace all 'a' with 'z'.

And you are given the integer $k$ — the maximum number of operations that can be performed. Find the minimum lexicographically possible string that can be obtained by performing no more than $k$ operations.

The string $a=a_1a_2 \dots a_n$ is lexicographically smaller than the string $b = b_1b_2 \dots b_n$ if there exists an index $k$ ($1 \le k \le n$) such that $a_1=b_1$, $a_2=b_2$, ..., $a_{k-1}=b_{k-1}$, but $a_k < b_k$.


-----Input-----

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

This is followed by descriptions of the test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the size of the string $s$ and the maximum number of operations that can be performed on the string $s$.

The second line of each test case contains a string $s$ of length $n$ consisting of lowercase Latin letters.

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


-----Output-----

For each test case, output the lexicographically minimal string that can be obtained from the string $s$ by performing no more than $k$ operations.


-----Examples-----

Input
4
3 2
cba
4 5
fgde
7 5
gndcafb
4 19
ekyv
Output
aaa
agaa
bnbbabb
aapp


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Spanning trees

String algorithms


Solutions:
def solve(s: str, k: int):
	if k >= 25:
		return 'a' * len(s)
	bottom = ord('a')
	for character in s:
		if k == 0:
			break
		character_order = ord(character)
		distance = character_order - bottom
		if distance <= 0:
			continue
		if distance <= k:
			k -= distance
			bottom = character_order
		else:
			while k > 0:
				next_character_order = character_order - 1
				next_character = chr(next_character_order)
				s = s.replace(character, next_character)
				character_order = next_character_order
				character = next_character
				k -= 1
	for character_order in range(bottom, ord('a'), -1):
		character = chr(character_order)
		s = s.replace(character, 'a')
	return s
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(solve(s, k))


def sol(s, n, k):
	if k >= 25:
		return 'a' * n
	toa = ord('a')
	tosec = -1
	tosec2 = -1
	sec = ''
	res = ''
	for i in range(n):
		tmp = ord(s[i])
		if tmp <= toa:
			res += 'a'
		elif tmp - toa <= k:
			k -= tmp - toa
			toa = tmp
			res += 'a'
		elif k > 0:
			tosec = tmp
			tosec2 = tosec - k
			sec = chr(tmp - k)
			k = 0
			res += sec
		elif tosec2 <= tmp <= tosec:
			res += sec
		else:
			res += s[i]
	return res
t = int(input())
for case in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	print(sol(s, n, k))


def res(s, n, k):
	mas = [ord(i) - ord('a') for i in s]
	i = 0
	while i < n and mas[i] <= k:
		i += 1
	if i == n:
		mas = [0] * n
	elif i == 0:
		pot = mas[0]
		pol = mas[0] - k
		for i in range(n):
			if pol <= mas[i] <= pot:
				mas[i] = pol
	else:
		pot1 = max(mas[:i])
		pot2 = mas[i]
		pol2 = mas[i] - (k - pot1)
		for i in range(n):
			if mas[i] <= pot1:
				mas[i] = 0
			elif pol2 <= mas[i] <= pot2:
				mas[i] = pol2
	s = ''.join((chr(i + ord('a')) for i in mas))
	return s
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(res(s, n, k))


base = ord('a')

def solve():
	(n, k) = map(int, input().split())
	ords = list(map(lambda c: ord(c) - base, input()))
	if k >= 25:
		print('a' * n)
		return
	zeros = 0
	addi = None
	for x in ords:
		if x <= zeros:
			continue
		if x - zeros <= k:
			cost = x - zeros
			zeros = x
			k -= cost
		else:
			addi = (x - k, x)
			break
	out = ''
	for x in ords:
		if x <= zeros:
			out += 'a'
		elif addi and addi[0] <= x <= addi[1]:
			out += chr(base + addi[0])
		else:
			out += chr(base + x)
	print(out)
for _ in range(int(input())):
	solve()


from string import ascii_lowercase

def index(char: str) -> int:
	return ord(char) - 97
results = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = [index(c) for c in input()]
	optimized = 0
	semi_optimized = None
	for i in range(n):
		if string[i] <= optimized:
			string[i] = 0
		elif k > 0:
			d = string[i] - optimized
			if d <= k:
				k -= d
				optimized = string[i]
				string[i] = 0
			else:
				semi_optimized = (string[i] - k, string[i])
				k = 0
	if semi_optimized is not None:
		for i in range(n):
			if semi_optimized[0] < string[i] <= semi_optimized[1]:
				string[i] = semi_optimized[0]
	results.append(''.join((ascii_lowercase[i] for i in string)))
print('\n'.join(results))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(lambda x: ord(x) - 97, input().strip()))
	largest = 0
	toward = 25
	second = 0
	for num in s:
		if num > largest:
			if num - k > 0:
				second = num
				toward = num - k + largest
				break
			else:
				largest = num
	res = []
	for idx in s:
		if idx <= largest:
			res.append('a')
		elif idx <= second:
			res.append(chr(min(toward, idx) + 97))
		else:
			res.append(chr(idx + 97))
	print(''.join(res))


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, k) = lii()
	s = llss()
	last = 0
	flag = True
	for (idx, i) in enumerate(s):
		val = ord(i) - 97
		if k >= val:
			last = max(last, val)
		else:
			flag = False
			break
	if flag:
		print('a' * n)
	else:
		res = s[:]
		for i in range(n):
			val = ord(s[i]) - 97
			if last >= val:
				res[i] = 'a'
		k = k - last
		if k > 0:
			curr = s[idx]
			chg = chr(ord(curr) - k)
			for j in range(n):
				if curr >= res[j]:
					res[j] = min(res[j], chg)
		print(''.join(res))


import math, bisect, heapq, random, sys, itertools
input = sys.stdin.readline

def gprint(t, ans=''):
	print(f'Case #{t + 1}:', ans)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
fact = [1]
ANS = []
for t in range(int(input())):
	(n, k) = ints()
	a = input().strip()
	a = list(a)
	if ord(a[0]) - ord('a') > k:
		(l, u) = (ord(a[0]) - k, ord(a[0]))
		c = chr(ord(a[0]) - k)
		b = ''
		for i in a:
			x = ord(i)
			if l <= x <= u:
				b += c
			else:
				b += i
		print(b)
	else:
		u = ord('z')
		kk = 0
		for i in a:
			if ord(i) - ord('a') > k:
				u = ord(i)
				k -= kk - ord('a')
				l = u - k
				c = chr(l)
				break
			kk = max(kk, ord(i))
		ans = ''
		for i in a:
			if ord(i) <= kk:
				ans += 'a'
			elif l <= ord(i) <= u:
				ans += c
			else:
				ans += i
		print(ans)


def solve(n, k, s):
	m = ord('a')
	for c in s:
		r = ord(c) - ord('a')
		if r <= k:
			m = max(ord(c), m)
		else:
			break
	j = k - (m - ord('a'))
	result = []
	for d in s:
		if ord(d) <= m:
			result.append('a')
		elif ord(d) <= ord(c) and ord(d) > ord(c) - j:
			result.append(chr(ord(c) - j))
		else:
			result.append(d)
	return ''.join(result)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(solve(n, k, s))


for test in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	res = ''
	m1 = 'a'
	m2 = 'a'
	for i in s:
		if k >= ord(i) - ord('a'):
			m1 = max(m1, i)
		else:
			m2 = i
			k = ord(m2) - k - ord('a')
			break
	for i in s:
		if i <= m1:
			res += 'a'
		elif i <= m2 and i > chr(ord(m1) + k):
			res += chr(ord(m1) + k)
		else:
			res += i
	print(res)


import sys
if len(sys.argv) == 2:
	sys.stdin = open(sys.argv[1])
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if k >= 25:
		print('a' * n)
		continue
	ans = ''
	max_s_under_k = None
	max_s_over_k = None
	min_s_over_k = None
	k_ = -1
	for i in range(n):
		if max_s_over_k is not None:
			if max_s_under_k is not None and s[i] <= max_s_under_k:
				ans += 'a'
			elif min_s_over_k <= s[i] <= max_s_over_k:
				ans += min_s_over_k
			else:
				ans += s[i]
		elif max_s_under_k is not None:
			if ord(s[i]) - ord('a') <= k:
				max_s_under_k = max(max_s_under_k, s[i])
				ans += 'a'
			else:
				max_s_over_k = s[i]
				k_ = k - (ord(max_s_under_k) - ord('a'))
				min_s_over_k = chr(ord(max_s_over_k) - k_)
				ans += min_s_over_k
		elif ord(s[i]) - ord('a') <= k:
			max_s_under_k = s[i]
			ans += 'a'
		else:
			max_s_over_k = s[i]
			k_ = k
			min_s_over_k = chr(ord(max_s_over_k) - k_)
			ans += min_s_over_k
	print(ans)


t = int(input())
l = 'abcdefghijklmnopqrstuvwxyz'
for k in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	s = input()
	arr = []
	for i in range(n):
		arr.append(s[i])
	if k >= 25:
		print(''.join(['a'] * n))
		continue
	ind = -1
	mx = 0
	for i in range(n):
		if ord(arr[i]) - 97 <= k:
			mx = max(ord(arr[i]) - 97, mx)
		else:
			ind = i
			break
	if ind == -1:
		print(''.join(['a'] * n))
		continue
	else:
		diff = k - mx
		char1 = arr[ind]
		char = l[ord(char1) - 97 - diff]
		for i in range(n):
			if ord(arr[i]) - 97 <= mx:
				arr[i] = 'a'
		for i in range(n):
			if arr[i] <= char1:
				if arr[i] >= char:
					arr[i] = char
		print(''.join(arr))
		continue


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = []
	if k >= 25:
		for i in range(n):
			a.append('a')
		print(''.join(a))
		continue
	val = []
	for i in range(n):
		val.append(ord(s[i]) - 97)
	used = 0
	index = -1
	notpossible = -1
	for i in range(n):
		if val[i] <= k:
			a.append('a')
			used = max(used, val[i])
		else:
			index = i
			notpossible = val[i]
			break
	if index == -1:
		print(''.join(a))
		continue
	possiblekaro = notpossible - (k - used)
	for i in range(index, n):
		if val[i] <= used:
			a.append('a')
		elif val[i] > possiblekaro and val[i] <= notpossible:
			a.append(chr(possiblekaro + 97))
		else:
			a.append(s[i])
	print(''.join(a))


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	if k >= 25:
		print('a' * n)
	else:
		p = 0
		m = 0
		r = 0
		for i in range(n):
			if ord(s[i]) - ord('a') > m:
				if ord(s[i]) - ord('a') - m > k:
					r = ord(s[i]) - ord('a') - k
					k = 0
					p = m + 0
					m = ord(s[i]) - ord('a')
					break
				else:
					k -= ord(s[i]) - ord('a') - m
					m = ord(s[i]) - ord('a')
		for i in range(26):
			if i <= p:
				s = s.replace(chr(ord('a') + i), 'a')
			elif r < i <= m:
				s = s.replace(chr(ord('a') + i), chr(ord('a') + r))
		print(s)


for t in range(int(input())):
	(n, k) = [int(l) for l in input().split()]
	s = [ord(l) - 97 for l in input()]
	m = max(s)
	if m <= k:
		print('a' * n)
		continue
	elif s[0] > k:
		m1 = s[0]
		low = m1 - k
		for i in range(0, n):
			if s[i] > low and s[i] <= m1:
				s[i] = low
		ans = ''
		for i in range(0, n):
			ans += chr(s[i] + 97)
		print(ans)
	else:
		f1 = -1
		for i in range(0, n):
			if s[i] > k:
				f1 = i
				break
		m1 = max(s[0:f1])
		for i in range(n):
			if s[i] <= m1:
				s[i] = 0
		k = k - m1
		n2 = s[f1]
		l_n2 = s[f1] - k
		for i in range(f1, n):
			if s[i] > l_n2 and s[i] <= n2:
				s[i] = l_n2
		k = 0
		ans = ''
		for i in range(0, n):
			ans += chr(s[i] + 97)
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	mx = 0
	for i in range(n):
		if ord(s[i]) - ord('a') > k:
			r = ord(s[i]) - ord('a')
			l = ord(s[i]) - ord('a') - (k - mx)
			an = ''
			for i in s:
				if ord(i) - ord('a') <= mx:
					an += 'a'
				elif ord(i) - ord('a') >= l and ord(i) - ord('a') <= r:
					an += chr(ord('a') + l)
				else:
					an += i
			print(an)
			break
		else:
			mx = max(mx, ord(s[i]) - ord('a'))
	else:
		print('a' * n)


iter = int(input())
base = ord('a')
for i in range(iter):
	x = input()
	x = x.split()
	num = int(x[1])
	onum = num
	string = input()
	mc = 'a'
	string = list(string)
	for i in range(len(string)):
		if ord(string[i]) - base > num:
			num -= ord(mc) - base
			for j in range(len(string)):
				if ord(mc) >= ord(string[j]):
					string[j] = 'a'
			mc = None
			val = ord(string[i])
			vals = chr(val - num)
			for j in range(i, len(string)):
				if ord(string[j]) <= val and ord(string[j]) > ord(vals):
					string[j] = vals
			break
		elif ord(string[i]) > ord(mc):
			mc = string[i]
	if mc is not None:
		print('a' * len(string))
		continue
	print(''.join(string))


t = int(input())

def f(len_s, n, s):
	s = [ord(e) - ord('a') for e in s]
	bar = 0
	lower_bound = 0
	upper_bar = 0
	upper_bound = 0
	for i in range(len(s)):
		if s[i] <= upper_bar:
			s[i] = min(s[i], upper_bound)
		if s[i] <= bar:
			s[i] = min(s[i], lower_bound)
		if not n:
			pass
		elif s[i]:
			if s[i] - n <= bar:
				n -= s[i] - bar
				bar = s[i]
				s[i] = lower_bound
			else:
				upper_bar = s[i]
				upper_bound = s[i] - n
				s[i] -= n
				n = 0
	ans = ''.join([chr(e + ord('a')) for e in s])
	return ans
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input().strip()
	print(f(n, k, s))


for _ in range(int(input())):
	(_, k) = map(int, input().split())
	s = [ord(x) - ord('a') for x in input()]
	m1 = 0
	for x in s:
		if x <= k:
			m1 = max(m1, x)
		else:
			(m2, m3) = (x - (k - m1), x)
			break
	t = map(lambda x: 0 if x <= m1 else m2 if m2 <= x <= m3 else x, s)
	print(''.join((chr(ord('a') + x) for x in t)))


test_cases = int(input())
for i in range(test_cases):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	(offset, curr, offset_aft_k, leftover_k, remaining, ans) = (0, ord(s[0]) - 97, 0, 0, 0, '')
	if curr > k:
		offset = curr - k
	else:
		remaining = k - curr
		for j in range(1, n):
			curr = ord(s[j]) - 97
			if remaining:
				if curr <= k:
					remaining = min(remaining, k - curr)
				else:
					offset_aft_k = curr - remaining
					leftover_k = remaining
					remaining = 0
			else:
				break
	if offset:
		first_letter = chr(97 + offset)
		for l in range(n):
			if offset <= ord(s[l]) - 97 <= offset + k:
				ans += first_letter
			else:
				ans += s[l]
	elif offset_aft_k:
		replacement = chr(97 + offset_aft_k)
		for l in range(n):
			curr = ord(s[l]) - 97
			if curr <= k - leftover_k:
				ans += 'a'
			elif offset_aft_k <= curr <= offset_aft_k + leftover_k:
				ans += replacement
			else:
				ans += s[l]
	else:
		for l in range(n):
			if ord(s[l]) - 97 <= k:
				ans += 'a'
			else:
				ans += s[l]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	maxSmb = 'z' if 97 + k > 122 else chr(97 + k)
	smb = 'a'
	lastSmb = 'a'
	for elm in s:
		if ord(elm) > ord(maxSmb):
			lastSmb = elm
			break
		if ord(smb) < ord(elm):
			smb = elm
	for ordSmb in range(ord(smb), ord('a'), -1):
		s = s.replace(chr(ordSmb), 'a')
		k -= 1
	newSmb = 97 if ord(lastSmb) - k < 97 else ord(lastSmb) - k
	for ordSmb in range(ord(lastSmb), newSmb, -1):
		s = s.replace(chr(ordSmb), chr(newSmb))
	print(s)


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

def cal(n, k, s):
	if k >= 25:
		return 'a' * n
	dic = defaultdict(list)
	p = []
	for (i, v) in enumerate(s):
		num = ord(v) - 97
		dic[num].append(i)
		if num not in p:
			p.append(num)
	if k >= max(p):
		return 'a' * n
	for i in range(len(p)):
		if p[i] > k:
			if i > 0:
				fn = max(p[:i])
				k -= fn
				for j in range(fn, 0, -1):
					if j not in dic:
						continue
					dic[0] += dic[j]
					del dic[j]
			ii = p[i]
			while k > 0:
				t = ii - 1
				if t in dic:
					dic[t] += dic[ii]
				else:
					dic[t] = dic[ii]
				del dic[ii]
				ii = t
				k -= 1
			break
	ans = [''] * n
	for i in dic.keys():
		for j in dic[i]:
			ans[j] = chr(i + 97)
	return ''.join(ans)
for jj in range(xx):
	(n, k) = [int(i) for i in input().split(' ')]
	s = input()
	print(cal(n, k, s))


for x in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s1 = 'a'
	s2 = 'a'
	s3 = 'a'
	for i in range(n):
		if ord(s[i]) - 97 <= k:
			if ord(s[i]) - 97 > ord(s1) - 97:
				s1 = s[i]
		else:
			k -= ord(s1) - 97
			s3 = s[i]
			s2 = chr(ord(s[i]) - k)
			break
	ans = [''] * n
	for i in range(n):
		if ord(s[i]) <= ord(s1):
			ans[i] = 'a'
		elif ord(s2) <= ord(s[i]) <= ord(s3):
			ans[i] = s2
		else:
			ans[i] = s[i]
	print(''.join(ans))


def useAll(s, k):
	return s
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	if k >= 25:
		print('a' * n)
	else:
		x = 0
		maxord = 0
		while x < n and ord(s[x]) - ord('a') <= k:
			maxord = max(maxord, ord(s[x]) - ord('a'))
			x += 1
		ans = ''
		for char in s:
			if ord(char) - ord('a') <= maxord:
				ans += 'a'
			else:
				ans += char
		k -= maxord
		s = ans[x:]
		ans = 'a' * x
		if s:
			currord = ord(s[0])
			for i in range(len(s)):
				if currord - k < ord(s[i]) <= currord:
					ans += chr(currord - k)
				else:
					ans += s[i]
		print(ans)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = (int(i) for i in input().split(' '))
	s = input()
	ans = list(s)
	l = ord('a')
	r1 = ord('z')
	r2 = r1
	for i in range(n):
		if k == 0:
			if ord(s[i]) > r1 and ord(s[i]) <= r2:
				ans[i] = chr(r1)
			elif ord(s[i]) <= l:
				ans[i] = 'a'
			else:
				ans[i] = s[i]
		elif l >= ord(s[i]):
			ans[i] = 'a'
		elif ord(s[i]) - l <= k:
			k -= ord(s[i]) - l
			l = ord(s[i])
			ans[i] = 'a'
		elif ord(s[i]) - l > k:
			r1 = ord(s[i]) - k
			r2 = ord(s[i])
			k = 0
			ans[i] = chr(r1)
	print(''.join(ans))


import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()
	s = S()
	a = [0] * 26
	for i in s:
		a[ord(i) - 97] += 1
	i = 25
	c = 0
	while i >= 0 and a[i] == 0:
		i -= 1
		c = i
	if k >= i:
		print('a' * n)
		continue
	b = [0] * 27
	ans = ''
	d = {}
	b[1] = 1
	for i in range(n):
		t = ord(s[i]) - 96
		p = t
		if b[t] > 0:
			ans += chr(b[t] + 96)
			continue
		while t >= 1 and b[t] == 0 and (k > 0):
			k -= 1
			t -= 1
		if b[t] == 0:
			b[t] = t
		while p >= t:
			b[p] = b[t]
			p -= 1
		ans += chr(96 + b[t])
	print(ans)


T = int(input())
q = []
for i in range(T):
	(s, n) = input().split()
	data = input()
	q.append((int(s), int(n), data))

def solve(s, n, data):
	first_tembus = ''
	highest_first = 'a'
	for c in data:
		if ord(c) - 97 > n:
			first_tembus = c
			break
		if ord(highest_first) < ord(c):
			highest_first = c
	if first_tembus != '':
		sisa = n - (ord(highest_first) - 97)
		target_tembus = chr(ord(first_tembus) - sisa)
	for c in data:
		if ord(highest_first) >= ord(c):
			print('a', end='')
		elif ord(c) >= ord(target_tembus) and ord(c) <= ord(first_tembus):
			print(target_tembus, end='')
		else:
			print(c, end='')
	print()
for (s, n, data) in q:
	solve(s, n, data)


t = int(input())
for t_item in range(t):
	(n, k) = map(int, input().split())
	if k > 25:
		k = 25
	s = input()
	m = dict()
	c = 'a'
	ind = -1
	for i in range(len(s)):
		if s[i] <= c:
			continue
		if ord(s[i]) - ord(c) <= k:
			k -= ord(s[i]) - ord(c)
			c = s[i]
		else:
			ind = i
			break
	if ind == -1:
		print('a' * n)
	else:
		print('a' * ind, end='')
		for i in range(ind, n):
			if s[i] <= c:
				print('a', end='')
			elif s[i] > s[ind]:
				print(s[i], end='')
			elif s[i] >= chr(ord(s[ind]) - k):
				print(chr(ord(s[ind]) - k), end='')
			else:
				print(s[i], end='')
		print()


from collections import defaultdict
from collections import deque
from sys import stdout
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = [ord(ch) for ch in input()]
	(from1, to1) = (-1, -1)
	(from2, to2) = (-1, -1)
	for i in range(n):
		s_i = s[i]
		if from1 <= s[i] <= to1:
			s[i] = from1
			continue
		if from2 <= s[i] <= to2:
			s[i] = from2
			continue
		if k == 0:
			continue
		if s[i] == ord('a'):
			continue
		if from1 == -1:
			from1 = max(s[i] - k, ord('a'))
			to1 = s[i]
			k -= s[i] - from1
			s[i] = from1
			continue
		if k >= s[i] - to1:
			k -= s[i] - to1
			to1 = s[i]
			s[i] = from1
			continue
		assert from2 == -1
		assert s[i] - k > to1
		from2 = s[i] - k
		to2 = s[i]
		k = 0
		s[i] = from2
	print(''.join(map(chr, s)))


f = lambda : input().strip()
t = int(f())
for i in range(t):
	(n, k) = map(int, f().split(' '))
	s = f()
	max_a = ord('a')
	min_cent = max_cent = ord('z') + 1
	cent = ''
	for c in s:
		oc = ord(c)
		if oc <= max_a:
			c = 'a'
		elif k > 0:
			dk = oc - max_a
			if k >= dk:
				max_a = oc
				k -= dk
				c = 'a'
			else:
				max_cent = oc
				min_cent = oc - k
				k = 0
				cent = c = chr(min_cent)
		elif min_cent <= oc <= max_cent:
			c = cent
		print(c, end='')
	print()


import sys

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

def solve(N, K, S):
	if K >= 25:
		return 'a' * N
	dp = {}
	for i in range(26):
		dp[chr(ord('a') + i)] = chr(ord('a') + i)
	ans = ''
	for s in S:
		if K > 0 and s == dp[s]:
			min_c = chr(ord('z') + 1)
			for i in range(min(26, K + 1)):
				curr_c = chr(max(ord('a'), ord(s) - i))
				to = dp[curr_c]
				if min_c == chr(ord('z') + 1) or to < dp[min_c]:
					min_c = curr_c
			diff = ord(s) - ord(min_c)
			target = dp[min_c]
			K -= diff
			for i in range(diff):
				dp[chr(ord(s) - i)] = target
		ans += dp[s]
	return ans
T = int(input())
for _ in range(T):
	(N, K) = get_ints()
	S = input().rstrip()
	print(solve(N, K, S))


import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict
from sys import stdin, stdout
import io
import math
import heapq
import bisect
import collections

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')

def get():
	return stdin.readline().rstrip()
mod = 10 ** 5 + 7
import random
random.random()
for _ in range(int(get())):
	(n, k) = map(int, get().split())
	s = get()
	d = defaultdict(str)
	ans = ''
	for i in range(26):
		d[chr(97 + i)] = chr(97 + i)
	for i in range(len(s)):
		x = s[i]
		s1 = set()
		while d[x] != 'a' and k > 0:
			if d[d[x]] == 'a':
				d[x] = 'a'
				break
			if chr(ord(d[x]) - 1) > d[x]:
				break
			s1.add(chr(ord(d[x])))
			d[x] = chr(ord(d[x]) - 1)
			k -= 1
		if d[d[x]] == 'a':
			d[x] = 'a'
		for i in s1:
			d[i] = min(d[x], d[i])
		ans = ans + d[x]
	print(ans)


t = int(input())
out = ''
ord_ = 'abcdefghijklmnopqrstuvwxyz'
order = {ord_[i]: i for i in range(len(ord_))}
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	string = input()
	ans = ''
	changed = [0] * 26
	for char in string:
		for i in range(max(1, order[char] - k + 1), order[char] + 1):
			if changed[i] == 0:
				k -= 1
			changed[i] = 1
		if k < 1:
			break
	map_ = {}
	last = 'a'
	for i in range(len(ord_)):
		if not changed[i]:
			map_[ord_[i]] = ord_[i]
			last = ord_[i]
		else:
			map_[ord_[i]] = last
	ans = ''
	for char in string:
		ans += map_[char]
	out += ans + '\n'
print(out)


def useAll(s, k):
	for i in range(k):
		char = ''
		for x in range(n):
			news = ''
			if s[x] != 'a':
				char = s[x]
				break
		if char:
			for e in range(n):
				if s[e] == char:
					news += chr(ord(char) - 1)
				else:
					news += s[e]
			s = news
	return s
r = int(input())
for _ in range(r):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	if k >= 25:
		print('a' * n)
	else:
		i = 0
		maxord = 0
		while i < n and ord(s[i]) - ord('a') <= k:
			maxord = max(maxord, ord(s[i]) - ord('a'))
			i += 1
		ans = ''
		for char in s:
			if ord(char) - ord('a') <= maxord:
				ans += 'a'
			else:
				ans += char
		k -= maxord
		ans = useAll(ans, k)
		print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline

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

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

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

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

def compress(root, x):
	if root[x] == x:
		return x
	root[x] = compress(root, root[x])
	return root[x]
t = inp()
for _ in range(t):
	(n, k) = inlt()
	_dict = defaultdict(list)
	s = input()
	if s[-1] == '\n':
		s = s[:len(s) - 1]
	s = list(s)
	root = [i for i in range(26)]
	index = 0
	while k > 0 and index < len(s):
		ch = s[index]
		idx = ord(ch) - ord('a')
		compress(root, idx)
		if root[idx] > 0:
			root[idx] = idx - 1
			s[index] = chr(root[idx] + ord('a'))
			k -= 1
		else:
			index += 1
	ans = ''
	for ch in s:
		idx = ord(ch) - ord('a')
		changed = compress(root, idx)
		ans += chr(changed + ord('a'))
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = [0] * 26
	for i in range(n):
		tmp = ord(s[i]) - ord('a')
		while tmp > 0 and k > 0 and (c[tmp] == 0):
			c[tmp] = 1
			k -= 1
			tmp -= 1
	d = {i: i for i in range(26)}
	for i in range(26):
		if c[i] == 0:
			tmp = i
		else:
			d[i] = tmp
	d = {chr(i + ord('a')): chr(d[i] + ord('a')) for i in range(26)}
	print(*[d[s[i]] for i in range(len(s))], sep='')


parent = []

def find(u):
	if u == parent[u]:
		return u
	parent[u] = find(parent[u])
	return parent[u]

def unite(u, v):
	u = find(u)
	v = find(v)
	if u == v:
		return 0
	if u > v:
		(u, v) = (v, u)
	parent[v] = u
	return 1
t = int(input())
while t > 0:
	parent = []
	for i in range(26):
		parent.append(i)
	t = t - 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	if k >= 25:
		for i in range(n):
			print('a', end='')
		print()
		continue
	for ch in s:
		u = ord(ch) - ord('a')
		if find(u) != 0:
			v = u - 1
			while v >= 0 and k:
				k -= unite(u, v)
				v = v - 1
	for ch in s:
		temp = ord('a') + find(ord(ch) - ord('a'))
		print(chr(temp), end='')
	print()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	dic = {}
	for j in range(97, 123):
		dic[chr(j)] = chr(j)
	for j in range(n):
		ele = dic[s[j]]
		no = ord(ele) - 97
		c = 0
		for g in range(ord(ele), 96, -1):
			if dic[chr(g)] != 'a':
				c += 1
			else:
				break
		if k >= c:
			k -= c
			for h in range(ord(ele), 96, -1):
				dic[chr(h)] = 'a'
		else:
			final = chr(ord(ele) - k)
			for h in range(ord(ele), ord(ele) - k, -1):
				dic[chr(h)] = final
			k = 0
	ans = ''
	for j in s:
		ans += dic[j]
	print(ans)


a = ord('a')
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	cost = [float('inf')] + [1] * 25
	s = []
	for x in input():
		x = ord(x) - a
		while k >= cost[x]:
			k -= cost[x]
			cost[x] = 0
			x -= 1
		s.append(x)
	print(''.join((chr(a + x) for x in s)))


for _ in range(int(input())):
	(_, k) = map(int, input().split())
	cost = [float('inf')] + [1] * 25
	for x in input():
		x = ord(x) - ord('a')
		while k >= cost[x]:
			k -= cost[x]
			cost[x] = 0
			x -= 1
		print(chr(ord('a') + x), end='')
	print()