题目内容

在蝴蝶悲园里，有一串写着小写字母的标牌。

你拿到一个长度为 $n$的字符串 $s$（下标从$1$到 $n$）。

你需要对字符串做 $k$ 次 “操作”。

一次操作的过程如下：你从左到右依次处理 $i=1,2,\dots,n$。

在一次操作中，按 $i=1,2,\dots,n$ 的顺序依次处理每个位置，每个位置的修改将立即生效并影响后续位置的统计：

• 令 $c$ 为当前位置 $i$ 的字符；
• 令 $x$ 为位置 $1$ 至 $i-1$ 中当前字符等于 $c$ 的数量；
• 令 $y$ 为位置 $i+1$至 $n$ 中当前字符等于 $c$ 的数量；
• 若 $x = y$，则将位置 $i$ 的字符修改为字母表中的下一个字母（'z' 变为 'a'），否则保持不变。

现在我们将按顺序执行 $k$ 次操作，请你输出做完$k$次操作后的最终字符串。

输入描述

每个测试文件均包含多组测试数据。

• 第一行输入一个整数

  $t\ (1 \le t \le 2 \times 10^5)$

  代表数据组数，每组测试数据描述如下：

  1. 第一行输入两个整数 $n$ 和 $k$$(1 \le n \le 10^5;\ 1 \le k \le 10^5)$，分别表示字符串长度与操作次数。
  2. 第二行输入一个长度为 $n$ 的字符串 $s$，保证仅由小写英文字母组成。

• 除此之外，保证单个测试文件的 $n$ 之和不超过 $10^5$，$k$ 之和不超过 $10^5$。

输出描述

对于每一组测试数据，新起一行输出做完$k$ 次操作后的最终字符串。

样例1

输入

2
2 1
ab
3 2
abc

输出

bb
bbe