A. Развлечение в ЦПМ
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поздравляю, вы поступили в Центр Помощи Магистрам! Однако, на уроках вам было безумно скучно и вам надоело ничего не делать, поэтому вы придумали себе развлечение.

Вам дана строка $$$s$$$ и чётное число $$$n$$$. Есть два типа операций, которые вы можете к ней применять:

  1. Добавить в конец строки $$$s$$$ перевёрнутую строку $$$s$$$ (например, если $$$s = $$$ cpm, то после применения операции $$$s = $$$ cpmmpc).
  2. Перевернуть текущую строку $$$s$$$ (например, если $$$s = $$$ cpm, то после применения операции $$$s = $$$ mpc).

Требуется определить лексикографически минимальную$$$^{\dagger}$$$ строку, которую можно получить после применения ровно $$$n$$$ операций. Обратите внимание, что вы можете применять операции разных типов в произвольном порядке, но суммарно вы должны применить ровно $$$n$$$ операций.

$$$^{\dagger}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ является префиксом $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое чётное число $$$n$$$ ($$$2 \leq n \leq 10^9$$$) — количество операций, применяемых к строке $$$s$$$.

Вторая строка каждого набора входных данных содержит одну строку $$$s$$$ ($$$1 \leq |s| \leq 100$$$), состоящую из строчных букв латинского алфавита, — строка, к которой применяются операции.

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

Для каждого набора входных данных выведите одну строку — лексикографически минимальную строку, которую можно получить после применения ровно $$$n$$$ операций.

Пример
Входные данные
5
4
cpm
2
grib
10
kupitimilablodarbuz
1000000000
capybara
6
abacaba
Выходные данные
cpm
birggrib
kupitimilablodarbuz
arabypaccapybara
abacaba
Примечание

В первом наборе входных данных можно применить операцию второго типа (то есть перевернуть строку $$$s$$$) $$$4$$$ раза. Тогда строка $$$s$$$ останется равной cpm.

Во втором наборе входных данных можно сделать следующее:

  • Применить операцию второго типа, после чего $$$s$$$ станет равной birg.
  • Применить операцию первого типа (то есть добавить в конец строки $$$s$$$ перевёрнутую строку $$$s$$$), после чего $$$s$$$ станет равной birggrib.