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

У Васи есть строка $$$s$$$ длины $$$n$$$. Он решает применить к ней следующее преобразование:

  1. Выберите целое $$$k$$$, ($$$1 \leq k \leq n$$$).
  2. Для $$$i$$$ от $$$1$$$ до $$$n-k+1$$$, переверните подстроку $$$s[i:i+k-1]$$$ строки $$$s$$$. К примеру, если строка $$$s$$$ равна qwer и $$$k = 2$$$, то строка пройдет следующую последовательность изменений:
    • qwer (начальная строка)
    • wqer (после переворачивания первой подстроки длины $$$2$$$)
    • weqr (после переворачивания второй подстроки длины $$$2$$$)
    • werq (после переворачивания последней подстроки длины $$$2$$$)
    Следовательно, получившаяся строка после преобразования $$$s$$$ с $$$k = 2$$$ равна werq.

Вася хочет выбрать такое $$$k$$$, чтобы строка, полученная в результате преобразования, была лексикографически минимальной возможной среди всех выборов $$$k$$$. Среди всех таких $$$k$$$ он хочет выбрать наименьшее. Так как он занят посещением Felicity 2020, он просит вашей помощи.

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

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

Каждый тест содержит несколько наборов входных данных.

Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 5000$$$). Далее следуют описания наборов входных данных.

Вторая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 5000$$$) — длину строки $$$s$$$.

Третья строка каждого набора входных данных содержит строку $$$s$$$ из $$$n$$$ строчных букв латинского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

Для каждого набора входных данных выведите две строки:

В первой строке выведите лексикографически минимально возможную строку $$$s'$$$, получающуюся как результат преобразования.

Во второй строке выведите подходящее значение $$$k$$$ ($$$1 \leq k \leq n$$$), которое вы выбрали для преобрразования. Если несколько значений $$$k$$$ дают лексикографически минимальную строку, выведите минимальное $$$k$$$ среди них.

Пример
Входные данные
6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p
Выходные данные
abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1
Примечание

В первом наборе тестовых данных примера, преобразование строки abab даст следующие результаты:

  • для $$$k = 1$$$ : abab
  • для $$$k = 2$$$ : baba
  • для $$$k = 3$$$ : abab
  • для $$$k = 4$$$ : baba

    Лексикографически наименьшая строка, которую можно получить  — это abab для $$$k = 1$$$ и $$$3$$$. Следовательно, наименьшее значение $$$k$$$ равно $$$1$$$.