You are given a string $S$ and an integer $L$. A operation is described as :- "You are allowed to pick any substring from first $L$ charcaters of $S$, and place it at the end of the string $S$. 
A string $A$ is a substring of an string $B$ if $A$ can be obtained from $B$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) elements from the end.
Find the lexographically smallest string after performing this opertaion any number of times (possibly zero).
For example $S$ = "codechef" and $L=4$. Then, we can take substring "ode" from S[0-3] and place it at end of the string $S$ = "cchefode".

-----Input:-----
- First line will contain $T$, number of testcases. 
- Then each of the N lines contain an integer $L$ and a string $S$. 

-----Output:-----
For each testcase, output in a single line answer lexographically smallest string.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $2 \leq |S| \leq 10^3$
- $1 \leq L \leq N $

-----Sample Input:-----
2
1 rga
2 cab

-----Sample Output:-----
arg
abc

-----EXPLANATION:-----
In the first testcase:
substring 'r' is picked and placed at the end of the string. rga -> gar
Then performing same operation gives :- gar -> arg

Difficulty: interview

Starter code:

Solutions:
def least_rotation(S: str) -> int:
    """Booth's algorithm."""
    f = [-1] * len(S)  # Failure function
    k = 0  # Least rotation of string found so far
    for j in range(1, len(S)):
        sj = S[j]
        i = f[j - k - 1]
        while i != -1 and sj != S[k + i + 1]:
            if sj < S[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != S[k + i + 1]:  # if sj != S[k+i+1], then i == -1
            if sj < S[k]:  # k+i+1 = k
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k


for _ in range(int(input())):
    l, s = input().split()
    if int(l) == 1:
        l = len(s)
        s += s
        k = least_rotation(s)
        print(s[k:k+l])
    else:
        print(''.join(sorted(s)))

import sys

def minshift(s):
	s += s
	n = len(s)
	i, ans = 0, 0
	while i < n//2:
		ans = i
		j, k = i+1, i
		while j<n and s[k] <= s[j]:
			if s[k] < s[j]:
				k = i
			else:
				k += 1
			j += 1

		while i <= k:
			i += j-k

	return s[ans:ans + n//2]

t = int(sys.stdin.readline().strip())
for _ in range(t):
	l, s = sys.stdin.readline().strip().split()
	l = int(l)

	arr = [0]*len(s)
	for i in range(len(s)):
		arr[i] = s[i]

	if l >= 2:
		arr.sort()
		print(*arr, sep='')
		print('')
	else:
		print(minshift(s))

		# minalph = min(arr)

		# pos = []

		# for i in range(len(s)):
		# 	if s[i] == minalph:
		# 		pos += [i]

		# # print(pos)

		# offset = 1
		# while True:
		# 	tempmin = 'z'
		# 	for i in range(len(pos)):
		# 		tempmin = min(tempmin, s[(pos[i]+offset)%len(s)])

		# 	temppos = []
		# 	for i in range(len(pos)):
		# 		if s[(pos[i]+offset)%len(s)] == tempmin:
		# 			temppos += [pos[i]]

		# 	pos = temppos[:]
		# 	offset += 1
		# 	# print(offset)
		# 	# print(pos)

		# 	if tempmin == minalph:
		# 		break

		# start = pos[0]
		# for i in range(len(s)):
		# 	print(s[(start+i)%len(s)], end='')
		# print('')

def least_rotation(S):
    S += S  # Concatenate string to it self to avoid modular arithmetic
    f = [-1] * len(S)  # Failure function
    k = 0  # Least rotation of string found so far
    for j in range(1, len(S)):
        sj = S[j]
        i = f[j - k - 1]
        while i != -1 and sj != S[k + i + 1]:
            if sj < S[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != S[k + i + 1]:  # if sj != S[k+i+1], then i == -1
            if sj < S[k]:  # k+i+1 = k
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

test = int(input())
for tc in range(test):
    l,st = input().split()
    l=int(l)
    if l==1:
        kk = least_rotation(st)
        ln = len(st)
        mt = ""
        for i in range(len(st)):
            mt+=str(st[(kk+i)%ln])
        print(mt)
    else:
        lst = []
        for i in range(len(st)):
            lst.append(st[i])
        lst.sort()
        mt = ""
        for i in range(len(lst)):
            mt+=str(lst[i])
        print(mt)

def least_rotation(S: str):
    """Booth's algorithm."""
    S += S  # Concatenate string to it self to avoid modular arithmetic
    f = [-1] * len(S)  # Failure function
    k = 0  # Least rotation of string found so far
    for j in range(1, len(S)):
        sj = S[j]
        i = f[j - k - 1]
        while i != -1 and sj != S[k + i + 1]:
            if sj < S[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != S[k + i + 1]:  # if sj != S[k+i+1], then i == -1
            if sj < S[k]:  # k+i+1 = k
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k
t=int(input())
for _ in range(t):
    l,s=input().split()
    l=int(l)
    n=len(s)
    if(l==1):
        o=least_rotation(s)
        s+=s
        print(s[o:o+n])
    else:
        v=''.join(sorted(s))
        print(str(v))

def least_rotation(S: str) -> int:
    """Booth's algorithm."""
    S += S  # Concatenate string to it self to avoid modular arithmetic
    f = [-1] * len(S)  # Failure function
    k = 0  # Least rotation of string found so far
    for j in range(1, len(S)):
        sj = S[j]
        i = f[j - k - 1]
        while i != -1 and sj != S[k + i + 1]:
            if sj < S[k + i + 1]:
                k = j - i - 1
            i = f[i]
        if sj != S[k + i + 1]:  # if sj != S[k+i+1], then i == -1
            if sj < S[k]:  # k+i+1 = k
                k = j
            f[j - k] = -1
        else:
            f[j - k] = i + 1
    return k

t=int(input())
for _ in range(t):
    l,s=input().split()
    if(l=='1'):
        k=least_rotation(s)
        ans=""
        n=len(s)
        s+=s
        for i in range(k,k+n):
            ans+=s[i]
        print(ans)
    else:
        s=sorted(s)
        print(''.join(s))

def solve(s,l,ans):
    n = len(s)
    s = list(s)
    if l > 1:
        s.sort()
        ans.append(s)
        return
    
    indices = []
    min_val = min(s)
    for i in range(len(s)):
        if s[i] == min_val:
            indices.append((i,1))


    while True:
        min_val = 'z'
        found = False
        for index,count in indices:
            min_val = min(min_val,s[index])
            if count == n:
                found = True
                
        if found:
            break

        new_indices = []
        for index,count in indices:
            if s[index] == min_val:
                if index+1 == n:
                    new_indices.append((0,count+1))
                else:
                    new_indices.append((index+1,count+1))

        indices = new_indices[:]

    s1 = []
    index = indices[0][0]
    count = 0
    while index >= 0:
        s1.append(s[index])
        count += 1
        index -= 1

    index = n-1
    while count != n:
        s1.append(s[index])
        index -= 1
        count += 1

    s1.reverse()
    ans.append(s1)

def main():
    t = int(input())
    ans = []
    for i in range(t):
        l,s = map(str,input().split())
        l = int(l)
        solve(s,l,ans)

    for i in ans:
        for j in i:
            print(j,end = '')

        print()


main()