Vasya has a string $s$ of length $n$. He decides to make the following modification to the string:   Pick an integer $k$, ($1 \leq k \leq n$).  For $i$ from $1$ to $n-k+1$, reverse the substring $s[i:i+k-1]$ of $s$. For example, if string $s$ is qwer and $k = 2$, below is the series of transformations the string goes through:   qwer (original string)  wqer (after reversing the first substring of length $2$)  weqr (after reversing the second substring of length $2$)  werq (after reversing the last substring of length $2$)  Hence, the resulting string after modifying $s$ with $k = 2$ is werq. 

Vasya wants to choose a $k$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $k$. Among all such $k$, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:   $a$ is a prefix of $b$, but $a \ne b$;  in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$. 


-----Input-----

Each test contains multiple test cases. 

The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5000$) — the length of the string $s$.

The second line of each test case contains the string $s$ of $n$ lowercase latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.


-----Output-----

For each testcase output two lines:

In the first line output the lexicographically smallest string $s'$ achievable after the above-mentioned modification. 

In the second line output the appropriate value of $k$ ($1 \leq k \leq n$) that you chose for performing the modification. If there are multiple values of $k$ that give the lexicographically smallest string, output the smallest value of $k$ among them.


-----Example-----
Input
6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p

Output
abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1



-----Note-----

In the first testcase of the first sample, the string modification results for the sample abab are as follows :   for $k = 1$ : abab  for $k = 2$ : baba  for $k = 3$ : abab  for $k = 4$ : baba

The lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$. Smallest value of $k$ needed to achieve is hence $1$.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    s = input().rstrip()
    words = []
    for i in range(n):
        if (n - i) % 2 == 0:
            words.append((s[i:] + s[:i], i+1))
        else:
            words.append((s[i:] + s[:i][::-1], i+1))
    words.sort()
    print(words[0][0])
    print(words[0][1])


for _ in range(int(input())):
    n = int(input())
    s = input()

    c = ''
    k = 0

    for i in range(n + 1):
        t = s[i:]

        if i % 2 != n % 2:
            t += s[:i][::-1]
        else:
            t += s[:i]

        if not c or t < c:
            c = t
            k = i

    print(c)
    print(k + 1)



t=int(input())
for nt in range(t):
    n=int(input())
    s=input()
    mr=s
    bk=1
    for k in range(2,n+1):
        p=s[k-1:]+(s[:k-1] if (n-k)%2 else s[:k-1][::-1])
        
        if (p<mr):
            mr=min(s,p)
            bk=k
    print(mr)
    print(bk)


t = int(input())
for _ in range(t):
  n = int(input())
  s = input()
  ans = [(s,1),(s[::-1],n)]
  for i in range(2,n):
    if (n-i+1)%2:
      x = "".join((s[i-1:],s[i-2::-1]))
      ans.append((x,i))
    else:
      x = "".join((s[i-1:],s[:i-1]))
      ans.append((x,i))
  ans.sort()
  print(*ans[0],sep="\n")


t = int(input())

for loop in range(t):

    n = int(input())

    s = input()


    lis = []

    for k in range(1,n+1):

        temp = list(s[:k-1])
        if (n-k+1) % 2 == 1:
            temp.reverse()
        ns = s[k-1:] + "".join(temp)
        lis.append([ns,k])

    lis.sort()
    print(lis[0][0])
    print(lis[0][1])


import sys
input = sys.stdin.readline


t = int(input())

for _ in range(t):
    n = int(input())
    a = input()
    tmp = a[0:]
    ans = -1
    for i in range(n):
        cnt = n - i
        if cnt % 2 == 0:
            if a[i:n] + a[0:i] < tmp:
                tmp = a[i:n] + a[0:i]
                ans = i
            
        else:
            if a[i:n] + a[0:i][::-1] < tmp:
                tmp = a[i:n] + a[0:i][::-1]
                ans = i
    print(tmp)
    print(ans + 1)


import io, sys, atexit, os
import math as ma
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations


def li():
    return list(map(int, sys.stdin.readline().split()))


def num():
    return list(map(int, sys.stdin.readline().split()))


def nu():
    return int(input())


def find_gcd(x, y):
    while (y):
        x, y = y, x % y
    return x


def lcm(x, y):
    gg = find_gcd(x, y)
    return (x * y // gg)


mm = 1000000007


def solve():
    t = nu()
    for tt in range(t):
        n=nu()
        s=input()
        mn=1
        val=s
        for i in range(2,n+1):
            x=s[0:i-1]
            y=s[i-1:]
            op=n-i+1
            if(op%2==0):
                up=y+x
            else:
                up=y+x[::-1]
            if(up<val):
                val=up
                mn=i
        print(val)
        print(mn)






def __starting_point():
    solve()

__starting_point()