题目描述

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$。

说明/提示

由 ChatGPT 4.1 翻译

样例

5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

codeforces
fft
algorithm
w
meetinthemiddle