Polycarp 有一个字符串 $$$s$$$,由小写拉丁字母组成。他使用以下算法对该字符串进行编码:
- 首先,他构造一个新的辅助字符串 $$$r$$$,它由字符串 $$$s$$$ 中所有不同的字母组成,按字母顺序书写;
- 然后编码如下:字符串 $$$s$$$ 中的每个字符都被字符串 $$$r$$$ 中的对称字符替换(字符串 $$$r$$$ 的第一个字符将被最后一个字符替换,第二个字符将被倒数第二个字符替换,依此类推)。
例如,对字符串 $$$s$$$="codeforces" 进行编码如下:
- 字符串 $$$r$$$ 被获取为“cdefors”;
- 第一个字符 $$$s_1$$$='c' 被 's' 替换;
- 第二个字符 $$$s_2$$$='o' 被 'e' 替换;
- 第三个字符 $$$s_3$$$='d' 被 'r' 替换;
- ...
- 最后一个字符 $$$s_{10}$$$='s' 被替换为 'c'。
字符串 $$$r$$$ 以及 $$$s$$$="codeforces" 的替换。
因此,对字符串 $$$s$$$="codeforces" 进行编码的结果是字符串“serofedsoc”。
编写一个执行解码的程序——即从编码结果中恢复原始字符串$$$s$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 字符串 $$$b$$$ 的长度。
每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$b$$$,由小写拉丁字母组成——原始字符串$$$s$$$编码的结果。
保证测试中所有测试用例的$$$n$$$值之和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出字符串$$$s$$$,从中获得编码结果$$$b$$$。
示例
输入 #1
5 10 serofedsoc 3 ttf 9 tlrhgmaoi 1 w 15 hnndledmnhlttin
输出 #1
codeforces fft algorithm w meetinthemiddle