311358: CF1974B. Symmetric Encoding

B. Symmetric Encodingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Polycarp has a string $s$, which consists of lowercase Latin letters. He encodes this string using the following algorithm:

• first, he constructs a new auxiliary string $r$, which consists of all distinct letters of the string $s$, written in alphabetical order;
• then the encoding happens as follows: each character in the string $s$ is replaced by its symmetric character from the string $r$ (the first character of the string $r$ will be replaced by the last, the second by the second from the end, and so on).

For example, encoding the string $s$="codeforces" happens as follows:

• the string $r$ is obtained as "cdefors";
• the first character $s_1$='c' is replaced by 's';
• the second character $s_2$='o' is replaced by 'e';
• the third character $s_3$='d' is replaced by 'r';
• ...
• the last character $s_{10}$='s' is replaced by 'c'.

The string $r$ and replacements for $s$="codeforces".

Thus, the result of encoding the string $s$="codeforces" is the string "serofedsoc".

Write a program that performs decoding — that is, restores the original string $s$ from the encoding result.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $b$.

The second line of each test case contains a string $b$ of length $n$, consisting of lowercase Latin letters — the result of encoding the original string $s$.

It is guaranteed that the sum of the values of $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.

Output

For each test case, output the string $s$ from which the encoding result $b$ was obtained.

ExampleInput

5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin

Output

codeforces
fft
algorithm
w
meetinthemiddle

题目大意：
波利卡普有一个由小写拉丁字母组成的字符串s。他使用以下算法对字符串进行编码：
1. 首先构建一个新的辅助字符串r，其中包含字符串s中所有不同的字母，按字母顺序排列；
2. 然后进行编码：字符串s中的每个字符都被字符串r中的对称字符替换（字符串r的第一个字符将被最后一个字符替换，第二个字符将被倒数第二个字符替换，依此类推）。

例如，对字符串s="codeforces"进行编码的过程如下：
- 获得字符串r="cdefors"；
- 第一个字符s1='c'被's'替换；
- 第二个字符s2='o'被'e'替换；
- 第三个字符s3='d'被'r'替换；
- ...
- 最后一个字符s10='s'被'c'替换。

因此，对字符串s="codeforces"进行编码的结果是字符串"serofedsoc"。

编写一个程序，进行解码，即从编码结果中恢复原始字符串s。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串b的长度。
- 每个测试用例的第二行包含一个长度为n的字符串b，由小写拉丁字母组成——原始字符串s的编码结果。
- 保证所有测试用例中n的值的总和不超过2×10^5。

输出：
- 对于每个测试用例，输出从编码结果b得到的原始字符串s。题目大意： 波利卡普有一个由小写拉丁字母组成的字符串s。他使用以下算法对字符串进行编码： 1. 首先构建一个新的辅助字符串r，其中包含字符串s中所有不同的字母，按字母顺序排列； 2. 然后进行编码：字符串s中的每个字符都被字符串r中的对称字符替换（字符串r的第一个字符将被最后一个字符替换，第二个字符将被倒数第二个字符替换，依此类推）。 例如，对字符串s="codeforces"进行编码的过程如下： - 获得字符串r="cdefors"； - 第一个字符s1='c'被's'替换； - 第二个字符s2='o'被'e'替换； - 第三个字符s3='d'被'r'替换； - ... - 最后一个字符s10='s'被'c'替换。 因此，对字符串s="codeforces"进行编码的结果是字符串"serofedsoc"。 编写一个程序，进行解码，即从编码结果中恢复原始字符串s。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——字符串b的长度。 - 每个测试用例的第二行包含一个长度为n的字符串b，由小写拉丁字母组成——原始字符串s的编码结果。 - 保证所有测试用例中n的值的总和不超过2×10^5。 输出： - 对于每个测试用例，输出从编码结果b得到的原始字符串s。