You have a string $s_1 s_2 \ldots s_n$ and you stand on the left of the string looking right. You want to choose an index $k$ ($1 \le k \le n$) and place a mirror after the $k$-th letter, so that what you see is $s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$. What is the lexicographically smallest string you can see?

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-----

The first line of input contains one integer $t$ ($1 \leq t \leq 10000$): the number of test cases.

The next $t$ lines contain the description of the test cases, two lines per a test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 10^5$): the length of the string.

The second line contains the string $s$ consisting of $n$ lowercase English characters.

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


-----Output-----

For each test case print the lexicographically smallest string you can see.


-----Examples-----

Input
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa
Output
cc
cbaabc
aa
bb


-----Note-----

In the first test case choose $k = 1$ to obtain "cc".

In the second test case choose $k = 3$ to obtain "cbaabc".

In the third test case choose $k = 1$ to obtain "aa".

In the fourth test case choose $k = 1$ to obtain "bb".

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
DEBUG = False

def Solve():
	n = int(input())
	S = input().strip()
	if n <= 1:
		return S[0] * 2
	if n >= 2:
		if S[0] == S[1]:
			return S[0] + S[1]
	for i in range(1, n):
		if S[i] <= S[i - 1]:
			continue
		else:
			return S[:i] + S[i - 1::-1]
	return S + S[::-1]
for _ in range(int(input())):
	print(Solve())


for s in [*open(0)][2::2]:
	a = (*map(ord, s[:-1]), 123)
	i = 1
	while (i > 1) + a[i - 1] > a[i]:
		i += 1
	s = s[:i]
	print(s + s[::-1])


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		n = get_int()
		s = get_string()
		ind = 0
		ans = ''
		for i in range(n - 1):
			if s[i] >= s[i + 1]:
				ind = i + 1
				ans += s[i]
			else:
				break
		ans += s[ind]
		if n == 1:
			get_print(ans + ans[::-1])
		elif s[0] != s[1]:
			get_print(ans + ans[::-1])
		else:
			get_print(s[0] + s[1])
solve()


for s in [*open(0)][2::2]:
	t = chr(ord(s[0]) - 1) + s[1:-1] + '~'
	i = 1
	while t[i - 1] >= t[i]:
		i += 1
	s = s[:i]
	print(s + s[::-1])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input()[:-1]
	if n == 1:
		print(s * 2)
	elif s[0] == s[1]:
		print(s[0] * 2)
	else:
		for i in range(n - 1):
			if s[i + 1] > s[i]:
				print(s[:i + 1] + s[:i + 1][::-1])
				break
		else:
			print(s + s[::-1])


import sys
input = sys.stdin.readline
read_int = lambda : int(input())

def main():
	for _ in range(read_int()):
		(n, s) = (read_int(), input())
		first = s[0] * 2
		second = '{'
		for i in range(n):
			if s[i] <= second[-1]:
				second += s[i]
			else:
				break
		second = second[1:]
		second += second[::-1]
		print(first if first < second else second)
main()


import sys

def N():
	return int(sys.stdin.readline())

def S():
	return sys.stdin.readline().rstrip()

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

def M():
	return map(int, sys.stdin.readline().split())
for _ in range(N()):
	n = N()
	s = S()
	if n == 1 or s[0] <= s[1]:
		print(s[0] + s[0])
		continue
	k = s[0]
	for i in range(1, n):
		if k[-1] >= s[i]:
			k += s[i]
		else:
			break
	print(k + k[::-1])


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	s = sys.stdin.readline().strip()
	if n == 1:
		print(s + s)
		continue
	if s[0] == s[1]:
		print(s[:2])
		continue
	index = len(s) - 1
	for i in range(1, n):
		if ord(s[i - 1]) < ord(s[i]):
			index = i - 1
			break
	print(s[:index + 1] + s[index::-1])


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	if n == 1 or s[0] <= s[1]:
		print(s[0] + s[0])
		continue
	ans = s[0]
	for i in range(1, n):
		if s[i] <= ans[-1]:
			ans += s[i]
		else:
			break
	print(ans + ans[::-1])


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	s = input().rstrip()
	ans = s[0]
	for i in range(1, n):
		if s[i] > s[i - 1]:
			break
		ans += s[i]
	if len(ans) == 1:
		print(ans * 2)
	elif ans[0] == ans[1]:
		print(s[0] * 2)
	else:
		print(ans + ans[::-1])


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = []
	p = 'z'
	for i in inp().strip():
		if i <= p:
			a.append(i)
		else:
			break
		p = i
	a = a + a[::-1]
	r = ''.join(a)
	print(min(r, a[0] + a[0]))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys, bisect, math
from collections import deque, Counter
input = lambda : sys.stdin.readline().strip()
ceil = lambda x: math.ceil(x)
mod = 10 ** 9 + 7

def solve():
	n = int(input())
	s = input()
	smallest = 0
	for i in range(1, n):
		if s[i - 1] > s[i]:
			smallest = i
		elif s[i - 1] < s[i]:
			break
		elif i == 1:
			break
		else:
			smallest = i
	return s[:smallest + 1] + s[:smallest + 1][::-1]
t = 1
t = int(input())
for _ in range(t):
	print(solve())


def mirror(s):
	if len(s) == 1:
		return s + s
	if s[0] == s[1]:
		return s[:2]
	i = 0
	length = len(s)
	while s[i] >= s[i + 1]:
		i += 1
		if i + 1 > length - 1:
			break
	st = s[:i + 1]
	rst = st[::-1]
	return st + rst
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	s = input()
	ans.append(mirror(s))
for i in ans:
	print(i)


def f(n, s):
	l = str(s[0])
	c = 0
	for i in range(1, n):
		if s[i] < s[i - 1]:
			l = l + str(s[i])
			c = 1
		elif s[i] > s[i - 1]:
			break
		elif c == 1:
			l = l + str(s[i])
		else:
			break
	k = ''.join(reversed(l))
	l = l + k
	return l
x = int(input())
m = []
for i in range(x):
	z = int(input())
	y = input()
	m.append((z, y))
for j in range(x):
	print(f(m[j][0], m[j][1]))


import collections

def mir_str(n, s):
	i = 1
	while i < len(s):
		if s[i] > s[i - 1]:
			break
		elif s[i] == s[i - 1]:
			if i == 1:
				break
		i = i + 1
	return s[:i] + s[:i][::-1]
t = int(input())
ln = []
ls = []
for x in range(t):
	n = int(input())
	s = str(input())
	ln.append(x)
	ls.append(s)
la = []
for i in range(len(ln)):
	n = ln[i]
	s = ls[i]
	ans = mir_str(n, s)
	la.append(ans)
for a in la:
	print(a)


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	n = inp_int()
	s = input().strip()
	if n == 1 or s[0] == s[1]:
		ans = s[0] + s[0]
		print(ans)
		continue
	ans = s[0]
	for i in range(1, n):
		if s[i] <= s[i - 1]:
			ans += s[i]
		else:
			break
	ans += ans[::-1]
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	go = False
	i = 1
	for i in range(1, n):
		if s[i] < s[i - 1]:
			go = True
			i += 1
		elif s[i] == s[i - 1] and go:
			i += 1
		else:
			break
	tg = s[:i]
	print(tg + tg[::-1])


import math, sys, collections
input = sys.stdin.readline
istr = lambda : input().strip()
inum = lambda : int(input().strip())
imap = lambda : map(int, input().strip().split())
ilist = lambda : list(map(int, input().strip().split()))
try:
	tcs = inum()
	for tc in range(tcs):
		n = inum()
		w = istr()
		ans = w[0]
		prv = w[0]
		flg = False
		for i in range(1, n):
			if w[i] < prv:
				flg = True
				ans += w[i]
				prv = w[i]
			elif flg:
				if w[i] == prv:
					ans += w[i]
				elif w[i] > prv:
					break
			else:
				break
		print(ans + ans[::-1])
except Exception as e:
	pass


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = insr()
	ans = l[0]
	temp = 1
	for i in range(1, n):
		if i == 1 and l[i - 1] == l[i]:
			break
		elif l[i - 1] >= l[i]:
			ans += l[i]
			temp += 1
		else:
			break
	print(ans + ans[::-1])


from collections import Counter
import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	string = input().strip()
	if n > 1 and string[0] == string[1]:
		print(string[0] * 2)
		continue
	i_last = n - 1
	prev = chr(ord('z') + 1)
	for (i, letter) in enumerate(string):
		if letter > prev:
			i_last = i - 1 if i > 0 else 0
			break
		prev = letter
	first_half = string[:i_last + 1]
	if first_half[0] == first_half[-1]:
		first_half = first_half[0]
	print(first_half + first_half[::-1])


t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	i = 0
	while i < n - 1 and s[i] >= s[i + 1]:
		if s[i] == s[i + 1] and i == 0:
			break
		i += 1
	ans = s[:i + 1]
	print(ans + ans[::-1])


t = int(input())
inputlist = []
for i in range(t):
	l = int(input())
	arr = input()
	inputlist.append(arr)
for q in inputlist:
	s = ''
	for j in range(len(q)):
		s += q[j]
		if j < len(q) - 1:
			if q[j] < q[j + 1]:
				break
			if q[j] == q[j + 1] and q[j] == q[0]:
				break
	print(s + s[::-1])


for _ in range(int(input())):
	n = int(input())
	s = input().strip()
	if n == 1:
		print(s * 2)
		continue
	if s[0] == s[1]:
		print(s[:2])
		continue
	for i in range(n - 1):
		if s[i] < s[i + 1]:
			break
	else:
		print(s + s[::-1])
		continue
	print(s[:i + 1] + s[i::-1])


t = int(input())
for _ in range(t):
	n = int(input())
	string = input()
	ans_ind = 0
	if n == 1:
		print(string + string)
	else:
		for i in range(1, n):
			if string[i - 1] > string[i] or (i != 1 and string[i - 1] == string[i]):
				ans_ind = i + 1
				continue
			ans_ind = i
			break
		ans = string[:ans_ind] + string[:ans_ind][::-1]
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		i = 0
	else:
		for i in range(n - 1):
			if s[i] < s[i + 1] or (s[i] <= s[i + 1] and s[0] <= s[i + 1]):
				break
		else:
			i += 1
	print(s[:i + 1] + s[:i + 1][::-1])


def solver():
	n = int(input())
	for _ in range(n):
		a = int(input())
		string = input()
		if a == 1:
			print(string + string)
			continue
		if string[0] == string[1]:
			print(string[0] + string[0])
		else:
			for ind in range(a - 1):
				if string[ind] < string[ind + 1]:
					printer = string[:ind + 1]
					printer1 = printer[::-1]
					print(printer + printer1)
					break
			else:
				print(string + string[::-1])
solver()


from audioop import reverse
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	j = 0
	while j < n - 1 and s[j] >= s[j + 1]:
		if s[j] == s[j + 1] and s[j] == s[0]:
			break
		j += 1
	out = s[:j + 1] + s[j::-1]
	print(out)


def solve():
	n = int(input())
	S = input()
	if n > 1 and S[0] == S[1]:
		return S[:2]
	for i in range(len(S)):
		if i + 1 == len(S) or S[i + 1] > S[i]:
			return S[:i + 1] + S[:i + 1][::-1]
t = int(input())
for _ in range(t):
	print(solve())


def wow():
	length = int(input())
	string = input()
	if length > 1 and string[0] == string[1]:
		return string[:2]
	for s in range(length):
		if s + 1 == length or string[s + 1] > string[s]:
			s1 = string[:s + 1]
			return s1 + s1[::-1]
t = int(input())
for i in range(t):
	print(wow())


for i in range(int(input())):
	input()
	(s, n) = (input(), 0)
	for j in range(1, len(s)):
		if s[j - 1] >= s[j] and s[j] != s[0]:
			n = j
		else:
			break
	print(s[:n + 1] + s[n::-1])


t = int(input())

def solve():
	n = int(input())
	s = input()
	ans = 0
	if n > 1 and s[0] == s[1]:
		print(s[0] + s[1])
		return
	while ans < n - 1:
		if ord(s[ans]) >= ord(s[ans + 1]):
			ans += 1
		else:
			break
	print(s[0:ans + 1] + s[0:ans + 1][::-1])
for i in range(t):
	solve()


import sys
for _ in range(int(input())):
	a = int(input())
	b = sys.stdin.readline().strip()
	x = b[0]
	for i in range(1, len(b)):
		if b[i] > b[i - 1] or x == b[i]:
			break
		else:
			x += b[i]
	print(x + x[::-1])


t = int(input())
for i in range(t):
	m = int(input())
	p = input()
	i = 1
	while i < m and (p[i - 1] > p[i] or (i > 1 and p[i] == p[i - 1])):
		i += 1
	print(p[:i] + p[i - 1::-1])


def solve():
	n = int(input())
	a = input()
	test = 0
	for x in range(1, n):
		if test == 0 and ord(a[x]) >= ord(a[test]):
			break
		elif ord(a[x]) <= ord(a[test]):
			test = x
		else:
			break
	a = a[:test + 1]
	a += a[::-1]
	print(a)
t = int(input())
for x124 in range(t):
	solve()


n = int(input())
for i in range(n):
	m = int(input())
	word = input()
	result = word[0]
	for j in range(1, m):
		if word[j] < result[-1]:
			result += word[j]
		elif word[j] == result[-1]:
			if j == 1:
				break
			else:
				result += word[j]
		else:
			break
	print(result + result[::-1])


t = int(input())
for test in range(t):
	n = int(input())
	l = input()
	least = l[0] + l[0]
	if len(l) == 1:
		print(least)
	elif l[0] == l[1]:
		print(least)
	else:
		it = 1
		current = l[0]
		next = l[1]
		while current >= next:
			it += 1
			if it == len(l):
				break
			current = next
			next = l[it]
		print(l[:it] + l[:it][::-1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	if len(s) > 1 and s[0] == s[1]:
		print(s[0] * 2)
	else:
		for i in range(n - 1):
			if s[i] < s[i + 1]:
				print(s[:i + 1] + s[i::-1])
				break
		else:
			print(s + s[::-1])


def solve():
	n = int(input())
	s = input()
	if n == 1:
		return s + s
	i = 1
	while s[i] <= s[i - 1] and s[i] != s[0]:
		i += 1
		if i == n:
			break
	return s[:i] + s[:i][::-1]
for _ in range(int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n != 1 and s[0] == s[1]:
		print(s[0] + s[0])
	else:
		prev = ord(s[0])
		ans = s[0]
		for i in s[1:]:
			if ord(i) > prev:
				break
			else:
				prev = ord(i)
				ans += i
		ans = ans + ans[::-1]
		print(ans)


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 1
	p = ord(s[0])
	if n > 1 and s[1] < s[0]:
		while i < n:
			if ord(s[i]) <= p:
				p = ord(s[i])
				i += 1
			else:
				break
	temp = s[:i]
	print(temp + temp[::-1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	k = 1
	if len(s) > 1 and s[0] != s[1]:
		current = s[0]
		for c in s[1:]:
			if c <= current:
				k += 1
				current = c
			else:
				break
	print(s[:k] + s[:k][::-1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(1, len(s)):
		if s[i] > s[i - 1] or (i == 1 and s[i] == s[i - 1]):
			k = i - 1
			break
	else:
		k = len(s) - 1
	print(s[:k + 1] + s[:k + 1][::-1])


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ind = 0
	ans = ''
	for i in range(n - 1):
		if s[i] >= s[i + 1]:
			ind = i + 1
			ans += s[i]
		else:
			break
	ans += s[ind]
	if n == 1:
		print(ans + ans[::-1])
	elif s[0] != s[1]:
		print(ans + ans[::-1])
	else:
		print(s[0] + s[1])


t = int(input())
while t > 0:
	n = int(input())
	s = str(input())
	k = 0
	while k < n - 1 and (s[k] > s[k + 1] or (s[k] == s[k + 1] and s[k] < s[0])):
		k += 1
	print(s[:k + 1] + s[:k + 1][::-1])
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	pre = s[0] + s[0]
	new = ''
	i = 0
	if n >= 2 and pre == (s[:2] + s[1::-1])[:2]:
		print(pre)
		t -= 1
		continue
	while i < n - 1 and s[i] >= s[i + 1]:
		i += 1
	print(s[:i + 1] + s[i::-1])
	t -= 1


a = 'abcdefghijklmnopqrstuvwxyz'
g = {}
for i in range(26):
	g[a[i]] = i
for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 1
	if n >= 2:
		if s[0] == s[1]:
			print(s[0], s[1], sep='')
			continue
	p = g[s[0]]
	while i < n:
		if g[s[i]] > p:
			break
		else:
			p = g[s[i]]
			i += 1
	print(s[:i] + s[:i][::-1], sep='')


for _ in range(int(input())):
	length = int(input())
	arr = input()
	if length == 1:
		print(arr * 2)
	else:
		flag = True
		for i in range(1, length):
			if arr[i] == arr[i - 1] and i == 1:
				print(arr[:2])
				flag = False
				break
			elif arr[i] <= arr[i - 1]:
				continue
			else:
				break
		if flag:
			if i < length - 1:
				temp = arr[:i]
				print(temp + temp[::-1])
			elif i == length - 1 and arr[i] <= arr[i - 1]:
				temp = arr[:i + 1]
				print(temp + temp[::-1])
			else:
				temp = arr[:i]
				print(temp + temp[::-1])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = 0
	rep = 0
	if n > 1 and s[0] == s[1]:
		print(s[:2])
	else:
		for j in range(1, n):
			if s[j - 1] < s[j]:
				print(s[:j] + s[j - 1::-1])
				flag = 1
				break
		if flag == 0:
			print(s[:] + s[::-1])


def solve():
	n = int(input())
	s = input()
	k = 1
	while k < n and (s[k] < s[k - 1] or (k > 1 and s[k] == s[k - 1])):
		k += 1
	ans = s[0:k]
	print(ans + ans[::-1])
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	s = input()
	ans = s[0]
	for j in range(1, n):
		if s[j] > ans[-1]:
			break
		ans += s[j]
	if len(ans) > 1 and ans[0] == ans[1]:
		print(ans[0] + ans[0])
		continue
	print(ans + ans[::-1])


from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
ceil_div = lambda a, b: -(-a // b)
mod = 10 ** 9 + 7
for _ in range(rn()):
	n = rn()
	s = rs()
	ans = s[0]
	for i in range(1, n):
		if s[i] < s[i - 1] or (s[i] == s[i - 1] and s[i] != ans[0]):
			ans += s[i]
		else:
			break
	print(ans + ans[::-1])


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
ls = lambda : list(input())
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve():
	for _ in range(inp()):
		n = inp()
		s = input()
		if n > 1 and s[0] == s[1]:
			print(s[:2])
			continue
		i = 0
		while i < n - 1:
			if s[i + 1] <= s[i]:
				i += 1
			else:
				break
		print(s[:i + 1] + s[:i + 1][::-1])
solve()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n == 1:
		print(s + s)
	elif s[0] == s[1]:
		print(s[0] + s[0])
	else:
		for i in range(1, n):
			if ord(s[i - 1]) >= ord(s[i]):
				i = i + 1
			else:
				break
		s = s[:i]
		print(s + s[::-1])


t = int(input())
for tt in range(t):
	n = int(input())
	a = input()
	ans = a[0]
	for r in range(1, n):
		if ord(a[r - 1]) > ord(a[r]):
			ans += a[r]
		elif ord(a[r - 1]) == ord(a[r]) and r != 1:
			ans += a[r]
		else:
			break
	ans += ans[::-1]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = str(s[0])
	beg = s[0]
	if n >= 2 and s[0] == s[1]:
		print(s[0] + s[0])
	else:
		for i in range(1, n):
			if s[i] <= beg:
				ans += s[i]
				beg = s[i]
			else:
				break
		ans2 = ans[::-1]
		print(ans + ans2)


from sys import stdin, stdout

def main():
	for _ in range(int(input())):
		n = int(input())
		a = input()
		if n == 1 or a[0] == a[1]:
			print(a[0] * 2)
			continue
		p = ord(a[0])
		s = 1
		for i in a[1:]:
			if ord(i) <= p:
				p = ord(i)
				s += 1
			else:
				break
		print(a[:s] + a[s - 1::-1])
main()


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ans = [s[0]]
	si = s[0]
	for sj in s[1:]:
		if si > sj or (si == sj and sj != s[0]):
			si = sj
			ans.append(si)
		else:
			break
	print(''.join(ans + ans[::-1]))


for _ in range(int(input())):
	n = int(input())
	s = input()
	ans = s[0]
	arr = [ord(s[0])]
	i = 1
	if n >= 2 and s[1] != s[0]:
		while i < n:
			if ord(s[i]) > ord(s[i - 1]):
				break
			ans += s[i]
			i += 1
	print(ans + ans[::-1])


t = int(input())
for case in range(t):
	n = int(input())
	s = str(input())
	k = 1
	if len(s) > 1 and s[0] != s[1]:
		i = 0
		while k < len(s) and s[i + 1] <= s[i]:
			i += 1
			k += 1
	ans = s[:k]
	print(ans + ans[::-1])


for _ in range(int(input())):
	n = int(input())
	s = input()
	index = 0
	if n == 1:
		print(s[0] * 2)
	elif s[1] >= s[0]:
		print(s[0] * 2)
	else:
		for i in range(1, n):
			if s[i - 1] >= s[i]:
				index = i
			else:
				break
		x = s[:index + 1]
		print(x + x[::-1])


def solve1():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		mx = 0
		ans = 1
		for i in range(1, n):
			if arr[i] - arr[i - 1] == 1:
				ans += 1
			else:
				mx = max(mx, ans)
				ans = 1
		mx = max(mx, ans)
		print(n - mx)

def solve():
	for _ in range(int(input())):
		n = int(input())
		s = input()
		ans = 0
		for i in range(1, n):
			if i == 1 and s[i] == s[i - 1]:
				break
			if s[i] <= s[i - 1]:
				ans += 1
			else:
				break
		t1 = s[:ans + 1]
		t2 = t1[::-1]
		temp = t1 + t2
		print(temp)
solve()


t = int(input())
for _ in range(t):
	n = int(input())
	str1 = input()
	i = 1
	ans = str1[0]
	while i < n:
		if str1[i - 1] > str1[i]:
			ans += str1[i]
		elif str1[i - 1] == str1[i] and i > 1:
			ans += str1[i]
		else:
			break
		i += 1
	temp = str1[:i]
	ans = temp + temp[::-1]
	print(ans)


for t in range(int(input())):
	n = input()
	a = input()
	str = a[0]
	ch = False
	for i in range(len(a) - 1):
		if a[i] < a[i + 1]:
			break
		if a[i] == a[i + 1] and ch == False:
			break
		else:
			ch = True
			str += a[i + 1]
	print(str + str[::-1])


for _ in range(int(input())):
	n = int(input())
	ll = list(input())
	n = len(ll)
	i = 0
	if n == 1:
		print(ll[0] + ll[0])
	elif ll[1] >= ll[0]:
		print(ll[0] + ll[0])
	else:
		while i <= n - 2:
			if ll[i] < ll[i + 1]:
				break
			elif ll[i + 1] < ll[i]:
				i += 1
			elif ll[i + 1] == ll[i]:
				for j in range(i + 1, n):
					if ll[j] > ll[i]:
						break
					elif ll[j] <= ll[i]:
						i = j
						continue
		mystr = ''.join(ll[:i + 1])
		print(mystr + mystr[::-1])


t = int(input())
for _ in range(t):
	n = int(input())
	str = input()
	if n == 0:
		print('')
		continue
	if n == 1:
		print(str[0] + str[0])
		continue
	ans = str[0]
	cnt = 0
	if str[0] == str[1]:
		print(str[0] + str[0])
		continue
	for i in range(1, n):
		if str[i] <= str[i - 1]:
			ans += str[i]
		else:
			break
	print(ans + ans[::-1])


t = int(input())
while t:
	sz = int(input())
	st = input()
	k = 0
	i = 0
	if sz == 1 or st[0] == st[1]:
		print(st[0] * 2)
		t -= 1
		continue
	while st[i] > st[i + 1] or st[i] == st[i + 1]:
		k = i + 1
		i += 1
		if i == sz - 1:
			break
	f = st[:k + 1]
	print(f + f[::-1])
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = input()
	if a == 'ggbois':
		print('Khairul Er Abba')
	c = a[0]
	if n >= 2:
		if a[0] > a[1]:
			temp = [a[0]]
			for i in range(1, n):
				if a[i] <= a[i - 1]:
					temp.append(a[i])
				else:
					break
			print(''.join(temp) + ''.join(temp[::-1]))
		else:
			print(a[0] + a[0])
	else:
		print(a[0] + a[0])


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)

def solve():
	n = int(input())
	s = input()
	k = 0
	cur = ''
	if n == 1 or s[0] == s[1]:
		return s[0] * 2
	for i in range(n - 1):
		cur += s[i]
		if s[i] < s[i + 1]:
			return cur + cur[::-1]
	return s + s[::-1]

def main():
	t = int(input())
	while t:
		print(solve())
		t -= 1
main()


T = int(input())
for t in range(T):
	N = int(input())
	S = input()
	k = 0
	while k < N - 1 and (S[k] > S[k + 1] or (S[k] == S[k + 1] and S[k] < S[0])):
		k += 1
	print(S[:k + 1] + S[:k + 1][::-1])


def fastsolution(s):
	ans = s[0]
	for i in range(1, len(s)):
		if s[i] == s[i - 1] and i == 1:
			break
		if s[i] > s[i - 1]:
			break
		ans += s[i]
	return ans + ans[::-1]
for _ in range(int(input())):
	n = int(input())
	s = input()
	ansfast = fastsolution(s)
	print(ansfast)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	cou = 0
	if n == 1:
		print(s[0] + s[0])
		continue
	if s[0] == s[1]:
		print(s[0] + s[1])
		continue
	for j in range(n - 1):
		if s[j] >= s[j + 1]:
			cou += 1
		else:
			break
	k = cou + 1
	print(s[:k] + s[k - 1::-1])


import math
for _ in range(int(input())):
	t = int(input())
	s = input()
	k = 0
	y1 = s[0]
	for i in range(1, t):
		if s[i - 1] < s[i] or s[i] == s[0]:
			break
		else:
			y1 += s[i]
	print(y1 + y1[::-1])