B. Left or Right Shift
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given a string $$$s$$$ of $$$n$$$ lowercase characters and an integer $$$k$$$.

In one operation, you can shift a character left, or shift a character right.

Shift a character left means shift $$$a$$$ to $$$z$$$,$$$b$$$ to $$$a$$$,...,or $$$z$$$ to $$$y$$$.

Shift a character right means shift $$$a$$$ to $$$b$$$,$$$b$$$ to $$$c$$$,...,or $$$z$$$ to $$$a$$$.

What is the lexographically smallest string you can obtain after exactly $$$k$$$ moves?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n,k$$$ ($$$1\le n \le 4 \cdot 10^5,1\le k \le 10^9$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ composed of lowercase letters.

The sum of $$$n$$$ over all test cases will not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, output on a new line — the lexographically smallest string you can obtain.

Example
Input
3
1 3
a
3 10
zkb
4 12
ycew
Output
b
abb
aaaa