B. Симметричное кодирование
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть строка $$$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$$$.

Вторая строка каждого набора содержит строку $$$b$$$ длины $$$n$$$, состоящую из строчных латинских букв — результат кодирования исходной строки $$$s$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите строку $$$s$$$ из которой был получен результат кодирования $$$b$$$.

Пример
Входные данные
5
10
serofedsoc
3
ttf
9
tlrhgmaoi
1
w
15
hnndledmnhlttin
Выходные данные
codeforces
fft
algorithm
w
meetinthemiddle