时空限制

1S/512M

题目描述

定义一个字符串序列 $s_0, s_1, s_2, \dots$。 给定一个初始字符串 $s_0$，该序列后续的字符串 $s_i$ (对于 $i \ge 1$) 由前一项 $s_{i-1}$ 按以下规则生成：

其中：

• + 代表字符串拼接。
• next(s) 是一个变换函数，它将字符串 s 中的每个字符替换为字母表中的下一个字符（最后一个字符变成第一个字符）。例如，a 会变为 b，b 会变为 c，z 会变为 a。

例如，如果 $s_{i-1}$ 是 azby，那么 $\text{next}(s_{i-1})$ 就是 bacz，因此 $s_i$ 为 azbyabacz。

对于给定的初始字符串 $s_0$ 和一个正整数 $k$，求出字符串 $s_{10^{100}}$ 中第 $k$ 个位置（字符串下标从 $1$ 开始）的字符。

格式

输入格式

本题包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据，第一行包含两个正整数 $|s_0|,k$，表示 $s_0$ 的长度和需要查询的位置。

第二行包含一个长度为 $|s_0|$ 的字符串 $s_0$。

输出格式

对于每组测试数据，输出一行，包含一个字符，表示所求的字符。

样例

样例输入 #1

4
1 6
c
2 4
ab
1 1
a
2 100000
nd

样例输出 #1

b
b
a
t

数据规模

对于 $30\%$ 的数据，$1 \leq T \leq 1000$，$1 \leq k \leq 1000$。

对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$1 \leq |s_0| \leq 10$，$1 \leq k \leq 10^{18}$，$s_0$ 仅由小写英文字母组成。