Chan has decided to make a list of all possible combinations of letters of a given string S. If there are two strings with the same set of characters, print the lexicographically smallest arrangement of the two strings. 

abc acb cab bac bca

all the above strings' lexicographically smallest string is abc. 

Each character in the string S is unique. Your task is to print the entire list of Chan's in lexicographic order. 

for string abc, the list in lexicographic order is given below

a ab abc ac b bc c

Input Format 

The first line contains the number of test cases T. T testcases follow. 

Each testcase has 2 lines. The first line is an integer N ( the length of the string). 

The second line contains the string S.  

Output Format 

For each testcase, print the entire list of combinations of string S, with each combination of letters in a newline.

Constraints 

0< T< 50 

1< N< 16 

string S contains only small alphabets(a-z) 

Sample Input

2
2
ab
3
xyz

Sample Output

a
ab
b
x
xy
xyz
xz
y
yz
z

Explanation 

In the first case we have ab, the possibilities are a, ab and b. Similarly, all combination of characters of xyz.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
T = int(input())
f = lambda x: [[y for (j, y) in enumerate(set(x)) if i >> j & 1] for i in range(2 ** len(set(x)))]
while T > 0:
	T -= 1
	N = input()
	x = input()
	a = f(x)
	for i in a:
		i.sort()
	a.sort()
	for i in a[1:]:
		for j in i:
			print(j, end='')
		print('')


import itertools
testcase = int(input())
for x in range(testcase):
	num = int(input())
	string = input()
	out = []
	for i in range(1, num + 1):
		for y in list(itertools.combinations(string, i)):
			out.append(''.join(y))
	out.sort()
	for i in out:
		print(i)


t = int(input())
import itertools

def func(lst):
	lst = sorted(list(lst))
	combs = []
	for i in range(1, len(lst) + 1):
		els = [''.join(list(x)) for x in itertools.combinations(lst, i)]
		combs.extend(els)
	combs.sort()
	for i in combs:
		print(i)
for i in range(t):
	input()
	func(input())


def lexorder(l):
	if len(l) == 1:
		return [l]
	else:
		front = l[0]
		rest = lexorder(l[1:])
		return [front + r for r in [''] + rest] + rest
n = int(input())
for i in range(1, n + 1):
	a = int(input())
	s = str(input())
	sorted(s)
	for r in lexorder(s):
		print(r)


import sys
import string

def generate_perms(string):
	perms = []
	for index in range(len(string)):
		perms += string[index]
		for perm in generate_perms(string[index + 1:]):
			perms += [str(string[index]) + ''.join(perm)]
	return perms
number_of_test_cases = int(sys.stdin.readline())
if number_of_test_cases not in range(1, 50):
	raise ValueError('Invalid number of tests.')
for test in range(number_of_test_cases):
	string_length = int(sys.stdin.readline())
	if string_length not in range(2, 16):
		raise ValueError('Invalid string length.')
	raw_string = sys.stdin.readline().rstrip('\n')
	bad_characters = [char for char in raw_string if char not in string.ascii_lowercase]
	if len(bad_characters) > 0:
		raise ValueError('String contained bad characters.')
	char_set = set(raw_string)
	if len(char_set) != len(raw_string):
		raise ValueError('String contained duplicate characters.')
	sorted_chars = sorted(raw_string)
	perms = '\n'.join(generate_perms(sorted_chars))
	print(perms)


import itertools
T = int(input())
for _ in range(T):
	N = int(input())
	s = input().strip()
	words = []
	for i in range(N + 1):
		L = list(itertools.combinations(s, i))
		words += [''.join(x) for x in L if x]
	words.sort()
	for w in words:
		print(w)


from itertools import chain, combinations
for s in range(int(input())):
	input()
	i = input()
	l = []
	m = []
	for z in chain.from_iterable((combinations(i, r) for r in range(len(i) + 1))):
		l.append(z)
	for i in l:
		k = ''
		for j in i:
			k = k + j
		m.append(k)
	m.sort()
	m.remove('')
	for i in m:
		print(i)


import itertools as itt
T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	print('\n'.join(sorted(list(set([''.join(x) for i in range(1, N + 1) for x in itt.combinations(S, i)])))))


def printComb(pref, chars):
	if not chars:
		return
	print(pref + chars[0])
	printComb(pref + chars[0], chars[1:])
	printComb(pref, chars[1:])
T = int(input())
for t in range(0, T):
	N = int(input())
	cs = input()
	printComb('', cs)


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


from itertools import combinations
lines = []
numberOfInputs = int(input())
for i in range(1, 2 * numberOfInputs + 1):
	lines.append(input())
ls = []
temp = []
while len(lines) > 0:
	charNum = lines.pop(0)
	str = lines.pop(0)
	for i in range(1, int(charNum) + 1):
		[temp.append(''.join(p)) for p in combinations(str, i)]
	temp.sort()
	for t in temp:
		ls.append(t)
	temp.clear()
for l in ls:
	print(l)


from itertools import combinations

def generate(string, length):
	li = []
	for val in range(1, length + 1):
		li.extend(combinations(string, val))
	li_ = sorted([''.join(sorted(ch)) for ch in li])
	print('\n'.join(li_))
num_test_cases = int(input())
for i in range(num_test_cases):
	length = int(input())
	string = input()
	generate(string, length)


from itertools import chain, combinations
import sys
next(sys.stdin)
try:
	while True:
		_ = next(sys.stdin)
		string = sorted(next(sys.stdin).strip())
		print('\n'.join(sorted(chain(*((''.join(perm) for perm in combinations(string, i)) for i in range(1, len(string) + 1))))))
except:
	pass


def getCombinations(cs):
	yield ()
	if cs:
		for s in getCombinations(cs[1:]):
			yield ((cs[0],) + s)
		for s in getCombinations(cs[1:]):
			if s and s[0] != cs[0]:
				yield s
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	for c in getCombinations(sorted(s)):
		if c:
			print(''.join(c))


import sys
from itertools import combinations

def comb_sort(string):
	collection = []
	for idx in range(1, len(string) + 1):
		for clump in combinations(string, idx):
			collection.append(''.join(clump))
	collection.sort()
	return collection

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		length = int(sys.stdin.readline())
		string = sys.stdin.readline().strip()
		for clump in comb_sort(string):
			print(clump)
main()


T = int(input())
for t in range(T):
	n = int(input())
	s = sorted(input())
	rr = []
	for i in range(1, 2 ** n):
		r = ''
		pos = 0
		x = i
		while x > 0:
			(x, f) = divmod(x, 2)
			if f:
				r += s[pos]
			pos += 1
		rr.append(r)
	for s in sorted(rr):
		print(s)


numtests = int(input())
tests = []
for i in range(numtests):
	input()
	tests.append(input())
for i in range(numtests):
	value = tests[i]
	binvalues = []
	for i in range(2 ** len(value)):
		x = list(bin(i))
		if len(x) - 2 < len(value):
			diff = len(value) - len(x) + 2
			for i in range(diff):
				x.insert(2, '0')
		binvalues.append(x)
	strcomb = []
	for el in binvalues:
		val = []
		for i in range(2, len(el)):
			if el[i] == '1':
				val.append(value[i - 2])
		strcomb.append(val)
	final = []
	for el in strcomb:
		x = ''.join(el)
		if x != '':
			final.append(x)
	y = sorted(final)
	for el in y:
		print(el)


def get_combos(S, N):
	S = list(reversed(sorted(S)))
	mask = '{{:0{}b}}'.format(N)
	for i in range(1, 2 ** N):
		keep = mask.format(i)
		result = ''.join(reversed([c for (n, c) in enumerate(S) if keep[n] == '1']))
		yield result
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	S = str(input().strip())
	for combo in sorted(get_combos(S, N)):
		print(combo)


T = int(input())
for t in range(T):
	N = int(input())
	letters = [letter for letter in str(input())]
	letters.sort(reverse=True)
	ret = [letters[0]]
	for i in range(1, len(letters)):
		tmp = []
		letter = letters[i]
		for suffix in ret:
			tmp.append(letter + suffix)
		tmp.append(letter)
		ret += tmp
	ret.reverse()
	for x in ret:
		print(x)


def actualize_bin_array(bin_array):
	for i in range(len(bin_array) - 1, -1, -1):
		bin_array[i] += 1
		if bin_array[i] > 1:
			bin_array[i] = 0
			continue
		else:
			break
	return bin_array

def test(word):
	bin_array = [0 for x in range(len(word))]
	n = 2 ** len(word)
	words = []
	for i in range(n):
		st = ''
		for i in range(len(bin_array)):
			if bin_array[i] == 1:
				st += word[i]
		if st != '':
			words.append(st)
		bin_array = actualize_bin_array(bin_array)
	words.sort(key=str.lower)
	return words
t = int(input())
for i in range(t):
	l = int(input())
	string = input()
	string = ''.join(sorted(string))
	words = test(string)
	for i in words:
		print(i)


def combinations(N, s):
	if N == 0:
		return {''}
	return {i for i in combinations(N - 1, s[:-1])} | {i + s[-1] for i in combinations(N - 1, s[:-1])}
T = int(input())
for i in range(T):
	N = int(input())
	s = input()
	c = combinations(N, s) - {''}
	l = list(c)
	l.sort()
	for e in l:
		print(e)


import itertools
tests = int(input())
for i in range(tests):
	Wlen = int(input())
	Word = input()
	List = []
	for i in range(1, Wlen + 1):
		x = itertools.combinations(Word, i)
		try:
			while True:
				List.append(''.join(next(x)))
		except:
			pass
	List.sort()
	for i in List:
		print(i)


import sys
t = int(sys.stdin.readline())

def go(cs, m=0, s='', length=0):
	if cs != '':
		print(cs)
	if m < length:
		for i in range(0, length):
			if m + i < length:
				go(''.join(cs + s[m + i]), m + i + 1, s, length)
n = sys.stdin.readline()
line = sys.stdin.readline()
while line:
	s = sorted(line.replace('\n', ''))
	go('', 0, s, len(s))
	n = sys.stdin.readline()
	line = sys.stdin.readline()


from itertools import chain, combinations

def powerset(iterable):
	s = list(iterable)
	return chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))
T = int(input())
res = []
for i in range(T):
	N = int(input())
	k = input().strip()
	s = sorted(list(k))
	strings = [''.join(i) for i in powerset(s)]
	res.append(sorted([''.join(list(i)) for i in strings if len(i) > 0]))
for p in res:
	for j in p:
		print(j)


def getList(s):
	if len(s) == 1:
		return [s]
	sublist = getList(s[1:])
	return [s[0]] + list(map(lambda item: s[0] + item, sublist)) + sublist
t = int(input())
for i in range(t):
	input()
	l = getList(input())
	for item in l:
		print(item)


from itertools import combinations

def lexicographic_list(word):
	strings = []
	for i in range(1, len(word) + 1):
		for comb in combinations(word, i):
			strings.append(''.join(comb))
	strings.sort()
	return strings
T = int(input())
cases = []
for i in range(T):
	N = int(input())
	cases.append(input())
for case in cases:
	print('\n'.join(lexicographic_list(case)))


def lex_list(char_list, cur_string):
	for i in range(len(char_list)):
		temp_str = cur_string + char_list[i]
		print(temp_str)
		lex_list(char_list[i + 1:], temp_str)
num_tests = int(input().strip())
for i in range(num_tests):
	str_len = int(input())
	string = list(input().strip())
	string.sort()
	lex_list(string, '')


from itertools import combinations
for i in range(int(input())):
	l = int(input())
	s = input()
	for a in sorted((''.join(e) for j in range(1, l + 1) for e in combinations(s, j))):
		print(a)


import itertools
for _ in range(int(input())):
	input()
	x = list(set(list(input())))
	res = []
	for i in range(1, len(x) + 1):
		res += [''.join(sorted(y)) for y in itertools.combinations(x, i)]
	res = sorted(res)
	for item in res:
		print(item)


T = int(input())

def all_permutes(s_head, s_tail):
	if s_head:
		print(''.join(s_head))
	if s_tail:
		for (i, t_n) in enumerate(s_tail):
			all_permutes(s_head + [t_n], s_tail[i + 1:])
	return
for i in range(T):
	N = input()
	s = sorted(input())
	all_permutes([], s)


def gen_combos(word, prefix=''):
	if not word:
		if prefix:
			return [prefix]
		else:
			return []
	return gen_combos(word[1:], prefix) + gen_combos(word[1:], prefix + word[0])
T = int(input())
for _ in range(T):
	input()
	word = sorted(input())
	print('\n'.join(sorted(gen_combos(word))))


from itertools import combinations
t = int(input())
for asdf in range(t):
	n = int(input())
	word = input()
	result = []
	for i in range(1, n + 1):
		result += combinations(word, i)
	result.sort()
	for item in result:
		print(''.join(item))


T = int(input())
assert 0 < T < 50
while T:
	N = int(input())
	assert 1 < N < 16
	str = list(input())
	str.sort()
	res = str[:]
	t = []
	for s in res:
		for (j, c) in enumerate(str):
			if str.index(s[-1]) < j:
				t.append(s + str[j])
		res.extend(t)
		t = []
	res.sort()
	for s in res:
		print(s)
	T -= 1


def strCombo(s, n):
	l = list(s)
	ret = list()
	if len(s) == 1:
		ret = [s]
	elif len(s) == 2:
		ret = [s]
		ret += [s[-1]]
		ret += [s[-2]]
		ret.sort()
	else:
		for i in range(1, 1 << n):
			st = ''
			for j in range(0, n):
				if i & 1 << j:
					st = st + s[j]
			ret += [st]
		ret.sort()
	return ret
t = int(input())
result = ''
printlist = []
for i in range(0, t):
	n = int(input())
	s = input()
	printlist = printlist + strCombo(s, n)
print('\n'.join(printlist))


T = int(input())

def permut(s, i, res):
	print(res + s[i])
	if i + 1 < len(s):
		permut(s, i + 1, res + s[i])
		permut(s, i + 1, res)
for t in range(T):
	N = int(input())
	S = input()
	permut(S, 0, '')


def strCombo(s, n):
	l = list(s)
	ret = list()
	if len(s) == 1:
		ret = [s]
	elif len(s) == 2:
		ret = [s]
		ret += [s[-1]]
		ret += [s[-2]]
		ret.sort()
	else:
		for i in range(1, 2 ** n):
			st = ''
			for j in range(0, n):
				if i & 2 ** j:
					st = st + s[j]
			ret += [st]
		ret.sort()
	return ret
t = int(input())
result = ''
printlist = []
for i in range(0, t):
	n = int(input())
	s = input()
	printlist = printlist + strCombo(s, n)
print('\n'.join(printlist))


from itertools import chain, tee

def subsets(s):
	if len(s) == 1:
		return s
	(sub, st) = tee(subsets(s[1:]))
	return chain(s[0], map(lambda x: s[0] + x, sub), st)
T = int(input())
for _ in range(T):
	input()
	for i in subsets(sorted(input())):
		print(i)


def get_comb(s):
	if len(s) == 1:
		return [s]
	else:
		char = s[0]
		combs = [char]
		parts = get_comb(s[1:])
		combs += [char + part for part in parts]
		combs += parts
		return combs
for _ in range(int(input())):
	n = int(input())
	s = input()
	combinations = get_comb(s)
	for combination in combinations:
		print(combination)


def do(current, pos, array):
	temp = ''
	temp += current + array[pos]
	print(temp)
	for i in range(pos + 1, len(array)):
		do(temp, i, array)
for _ in range(int(input())):
	n = int(input())
	hold = list(input())
	for i in range(len(hold)):
		do('', i, hold)


def myBin(num, countBit):
	b = [0] * countBit
	t = str(bin(num))[2:]
	for i in range(0, countBit, 1):
		if i < len(t):
			b[~i] = int(t[~i])
	return b

def subSets(n, s):
	lst = []
	for i in range(1, 1 << n):
		k = myBin(i, n)
		sub = ''
		for ch in range(len(k)):
			if k[ch] == 1:
				sub += s[ch]
		lst.append(sub)
	return sorted(lst)
for t in [1] * int(input()):
	print(*subSets(int(input()), sorted(input())), sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ans = []
	for i in range(1, 2 ** n):
		str = []
		for j in range(n):
			if i & 1 << j != 0:
				str.append(s[j])
		ans.append(''.join(str))
	ans.sort()
	print('\n'.join(ans))


import itertools
T = int(input())
for i in range(T):
	N = int(input())
	s = input()
	combs = []
	for j in range(1, N + 1):
		combs += list(itertools.combinations(s, j))
	combs = map(list, combs)
	combs = list(map(lambda x: ''.join(sorted(x)), combs))
	for comb in sorted(combs):
		print(comb)


def filter_length(S, L):
	out = []
	for item in S:
		if len(item) == L:
			out.append(item)
	return out
T = int(input())
for t in range(T):
	N = int(input())
	s = list(input())
	s.sort()
	combinations = []
	for i in s:
		combinations.append(i)
	for i in range(1, N):
		new = []
		temp = filter_length(combinations, i)
		for letter in s:
			for item in temp:
				if letter not in item and letter < item:
					new.append(letter + item)
		for item in new:
			combinations.append(item)
	combinations.append(''.join(s))
	combinations = list(set(combinations))
	combinations.sort()
	for item in combinations:
		print(item)


import sys
from itertools import chain, combinations
strcombinations = lambda s, x: (''.join(_) for _ in combinations(s, x))

def process_testcase():
	length = int(sys.stdin.readline())
	string = sys.stdin.readline().strip()
	if len(string) != length:
		raise Exception('Invalid length')
	else:
		allperms = chain(*(strcombinations(string, x) for x in range(1, length + 1)))
		print('\n'.join(sorted(allperms)))
t = int(sys.stdin.readline())
for i in range(t):
	process_testcase()


T = int(input())
s_list = []
for _ in range(T):
	n = int(input())
	s_list.append(input())
from itertools import combinations
for s in s_list:
	temp = []
	for n in range(len(s)):
		for c in combinations(s, n + 1):
			temp.append(c)
	for s in sorted(temp):
		print(''.join(s))


from itertools import combinations
t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip()
	assert n == len(s), 'Bad string length.'
	combs = []
	for j in range(1, n + 1):
		combs += [''.join(list(tup)) for tup in combinations(s, j)]
	combs.sort()
	for c in combs:
		print(c)


import itertools

def listy(stra):
	lo = []
	for i in range(1, len(stra) + 1):
		lo = lo + [''.join(x) for x in itertools.combinations(stra, i)]
	return lo
tc = int(input())
k = []
for i in range(tc):
	n2 = int(input())
	lo2 = listy(input())
	lo2.sort()
	k = k + lo2
for st in k:
	print(st)


import itertools

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		s = input()
		sl = list()
		for i in range(n):
			for ss in itertools.combinations(s, i + 1):
				sl.append(''.join(ss))
		sl.sort()
		for j in sl:
			print(j)
main()


def Permute(n, s):
	ans = []
	for e in range(1 << n):
		ans.append(''.join((s[b] for b in range(0, n) if e & 1 << b)))
	ans.sort()
	for i in ans:
		if i:
			print(i)
for _ in range(int(input())):
	Permute(int(input()), input())


from itertools import combinations

def lexico_combination(Str, Str_len):
	lis = []
	for i in range(Str_len):
		combination = (c for c in combinations(Str, i + 1))
		for j in combination:
			lis.append(''.join(j))
	lis1 = sorted(lis)
	for X in lis1:
		print(X)
TC = int(input())
for i in range(TC):
	Str_len = int(input())
	Str = input()
	lexico_combination(Str, Str_len)


def f(i, x, text):
	if 1 << i & x > 0:
		return text[i]
	else:
		return ''

def g(text):
	length = len(text)
	return sorted([''.join([f(i, j, text) for i in range(length)]) for j in range(2 ** length)])[1:]

def print_solution(text):
	lst = g(text)
	for t in lst:
		print(t)
n = int(input().strip())
for i in range(n):
	unused = input()
	print_solution(input().strip())


def combination(string, allowed):
	if not allowed:
		return
	else:
		for (idx, char) in enumerate(allowed):
			buf.append(char)
			print(''.join(map(str, buf)))
			combination(string, allowed[idx + 1:])
			buf.remove(char)
t = int(input())
for _ in range(t):
	n = input()
	string = input()
	allowed = list(string)
	buf = []
	combination(string, allowed)


for _ in range(int(input().strip())):
	l = int(input().strip())
	s = ''.join(sorted(input().strip()))
	strings = [''.join(reversed(bin(i)[2:])) for i in range(1, 2 ** l)]
	strings = sorted([[idx for (idx, l) in enumerate(s) if '0' != l] for s in strings])
	for out in strings:
		print(''.join([s[idx] for idx in out]))


def print_sub(string, prefix=''):
	if string == '':
		pass
	for (i, ch) in enumerate(string):
		print(prefix + ch)
		print_sub(string[i + 1:], prefix + ch)
for _ in range(int(input())):
	n = int(input())
	string = ''.join(sorted(list(input())))
	print_sub(string)


from itertools import combinations
for _ in range(int(input())):
	stringSize = int(input())
	string = input().rstrip('\n')
	combos = []
	for r in range(1, len(string) + 1):
		combos += (''.join(s) for s in combinations(string, r))
	combos.sort()
	print('\n'.join(combos))


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


testcases = int(input())
for i in range(0, testcases):
	stringlength = int(input())
	string = str(input())
	top = bin(2 ** stringlength - 1)
	answer = []
	while int(top, 2) > 0:
		tmp = top.split('b')
		tmp = tmp[1].zfill(stringlength)
		answer.append('')
		for j in range(0, len(tmp)):
			if tmp[j] == '1':
				answer[len(answer) - 1] = answer[len(answer) - 1] + str(string[j])
		top = bin(int(top, 2) - 1)
	answer.sort()
	for k in range(0, len(answer)):
		print(str(answer[k]))


import itertools
for _ in range(int(input())):
	n = int(input())
	letters = list(input())
	letters.sort()
	combs = []
	for i in range(1, n + 1):
		for comb in itertools.combinations(letters, i):
			line = ''.join(comb)
			combs.append(line)
	combs.sort()
	for c in combs:
		print(c)


import itertools
for _ in range(int(input())):
	N = int(input())
	string = input()
	res = []
	for i in range(1, N + 1):
		strings = itertools.combinations(string, i)
		for item in strings:
			res.append(''.join(item))
	for data in sorted(res):
		print(data)


def printLex(prefix, tail):
	print(prefix)
	if not tail:
		return
	else:
		for (i, e) in enumerate(tail):
			printLex(prefix + e, tail[i + 1:])
numcases = int(input())
for i in range(numcases):
	_ = input()
	line = input()
	for (i, e) in enumerate(line):
		printLex(e, line[i + 1:])


numtest = int(input())
for z in range(numtest):
	l = int(input())
	s = input()
	ans = set([])
	for j in range(1, 2 ** l + 1):
		i = j
		n = l - 1
		tmp = ''
		while i > 0:
			if i & 1 == 1:
				tmp += s[n]
			i = i >> 1
			n -= 1
		ans.add(''.join(sorted(tmp)))
	ans = sorted(ans)
	for i in ans:
		print(i)


from itertools import combinations
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	l = []
	for i in range(1, n + 1):
		l += list(combinations(s, i))
	l = [''.join(x) for x in l]
	for x in sorted(l):
		print(x)


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


from itertools import combinations
numTests = int(input())
for test in range(numTests):
	length = int(input())
	string = input()
	sequences = []
	for ix in range(1, length + 1):
		for p in combinations(string, ix):
			p = list(p)
			p.sort()
			sequences.append(''.join(p))
	sequences.sort()
	for s in sequences:
		print(s)


t = int(input())
for m in range(0, t):
	ls = []
	n = int(input())
	s = input()
	k = pow(2, n)
	for i in range(1, k):
		x = '{:016b}'.format(i)
		string = ''
		for p in range(0, n):
			if x[16 - n + p] == '1':
				string += s[p]
		ls.append(string)
	ls.sort()
	for c in ls:
		print(c)


import itertools
cases = int(input())
answers = []
for i in range(0, cases):
	numChars = int(input())
	myString = input()
	myList = []
	for j in range(1, numChars + 1):
		myList.extend((''.join(k) for k in itertools.combinations(myString, j)))
	answers.extend((''.join(k) for k in sorted(myList)))
for i in answers:
	print(i)


import itertools
num_tests = int(input())
output = []
for test in range(num_tests):
	temp = []
	num_chars = int(input())
	list_of_chars = input()
	for i in range(1, num_chars + 1):
		temp.extend(itertools.combinations(list_of_chars, i))
	output.extend(sorted([''.join(j) for j in temp]))
for combination in output:
	print(combination)


import itertools

def get_perms(s):
	result = set()
	for i in range(1, len(s) + 1):
		combs = itertools.combinations(s, i)
		result = result | set([''.join(s) for s in list(combs)])
	return result
T = int(input())
while T > 0:
	n_letters = int(input())
	res_string = input()
	res_set = get_perms(res_string)
	res_list = sorted(list(res_set))
	for res in res_list:
		print(res)
	T -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	S = sorted(input())
	strs = []
	l = 0
	for i in range(N):
		for j in range(l):
			strs.append(strs[j] + S[i])
			l += 1
		strs.append(S[i])
		l += 1
	strs.sort()
	for s in strs:
		print(s)


def dfs(idx, a, s, n, se):
	if idx == n:
		return
	se.add(a + s[idx])
	for i in range(idx + 1, n):
		dfs(i, a + s[idx], s, n, se)
	for i in range(idx + 1, n):
		dfs(i, a, s, n, se)

def do(n, s):
	se = set()
	s = sorted(s)
	dfs(0, '', s, n, se)
	for v in sorted(se):
		print(v)
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	do(n, s)


T = int(input())
for t in range(T):
	input()
	s = sorted(input())
	res = [[s[j] for j in range(len(s)) if i >> j & 1] for i in range(1, 1 << len(s))]
	for i in sorted(res):
		print(*i, sep='')


from itertools import chain, combinations

def powerset(iterable):
	s = list(iterable)
	return chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))

def main():
	t = int(input())
	for i in range(0, t):
		n = int(input())
		s = input()
		x = list(map(''.join, powerset(s)))
		x = sorted(x)
		x.remove('')
		l = len(x)
		for j in range(0, l):
			print(x[j])
main()


from itertools import combinations
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	t = []
	for j in range(1, n + 1):
		for c in combinations(s, j):
			t.append(''.join(c))
	t = sorted(t)
	for i in t:
		print(i)


import itertools
T = int(input())
for _ in range(T):
	N = int(input())
	s = list(str(input()).strip())
	s = sorted(s)
	ans = []
	for i in range(1, N + 1):
		res = list(itertools.combinations(s, i))
		ans += res
	ans = sorted(ans)
	for a in ans:
		print(''.join(a))


import itertools
n = int(input())
for _ in range(n):
	l = int(input())
	string1 = list(input())
	strings = []
	for i in range(1, l + 1):
		combinations = list(itertools.combinations(string1, i))
		for item in combinations:
			strings.append(''.join(item))
	strings.sort()
	for string in strings:
		print(string)


import itertools

def stringify(L):
	s = ''
	for i in L:
		s = s + str(i)
	return s

def string_combos(s):
	combos = []
	for i in range(1, len(s) + 1):
		for j in itertools.combinations(s, i):
			combos.append(stringify(j))
	combos.sort()
	for i in combos:
		print(i)
	return
num_trials = int(input())
L = []
for i in range(num_trials):
	length = input()
	string = input()
	L.append(string)
for i in L:
	string_combos(i)


def fun(check):
	size = 2 ** len(check)
	ans = []
	for i in range(size):
		s = ''
		for j in range(len(check)):
			if i & 1 << j:
				s = s + check[j]
		ans.append(s)
	ans = sorted(ans)
	for i in ans:
		if i != '':
			print(i)
temp = []
t = int(input())
while t:
	t = t - 1
	n = int(input())
	temp = input()
	fun(temp)


for i in range(int(input())):
	N = int(input())
	string = sorted(input())
	res = []
	for i in range(1, 2 ** N):
		res.append(''.join((string[letter] for letter in range(len(string)) if i // 2 ** letter % 2 == 1)))
	print('\n'.join(sorted(res)))


import itertools, sys
T = int(input())
for i in range(T):
	N = int(sys.stdin.readline())
	S = input().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


def get1():
	return int(input())

def solve(n, s):
	s = sorted(s)
	r = []
	for i in range(1, 2 ** n):
		k = []
		for j in range(n):
			if i & 1 << j:
				k.append(s[j])
		r.append(''.join(k))
	r.sort()
	for k in r:
		print(k)

def main():
	t = get1()
	for i in range(t):
		n = get1()
		s = input()
		solve(n, s)
main()


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


from itertools import *
t = int(input().strip())
for tt in range(t):
	p = int(input().strip())
	st = input()
	sts = sorted(st)
	st = ''.join(sts)
	res = []
	for i in range(1, len(st) + 1):
		for j in combinations(st, i):
			stc = ''.join(j)
			res.append(stc)
	res.sort()
	for x in res:
		print(x)


def substrs(input):
	if len(input) == 1:
		return input
	c = input[0]
	s2 = substrs(input[1:])
	combined = [c + x for x in s2]
	combined.insert(0, c)
	combined = combined + s2
	return combined
T = int(input())
for _ in range(T):
	n = input()
	s = sorted(list(input()))
	subs = substrs(s)
	for s1 in subs:
		print(s1)


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


import itertools
t = int(input())
for ii in range(0, t):
	n = int(input())
	s = input()
	ar = list(s)
	ar.sort()
	c = []
	for i in range(1, n + 1):
		l = list(itertools.combinations(ar, i))
		[c.append(''.join(i)) for i in l]
	c.sort()
	[print(i) for i in c]


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


for _ in range(int(input())):
	input()
	s = ''.join(sorted(input()))
	rev = [s[-1]]
	for i in range(len(s) - 2, -1, -1):
		rev = [s[i]] + [s[i] + el for el in rev] + rev
	for el in rev:
		print(el)


from itertools import chain, combinations

def powerset(iterable):
	s = list(iterable)
	l = list(map(''.join, chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))))
	l = [x for x in l if x]
	l.sort()
	for w in l:
		print(w)
n = input()
for i in range(int(n)):
	n1 = input()
	my_str = input()
	powerset(my_str)


def print_combinations(combinations):
	for combination in combinations:
		print(''.join(combination))

def list_combinations(sequence):

	def combine(pool):
		if not pool:
			return []
		(head, tail) = (pool[0:1], pool[1:])
		combinations = [head]
		pools = combine(tail)
		for apool in pools:
			combinations.append(head + apool)
		combinations.extend(pools)
		return combinations
	return combine(sorted(sequence))
num_cases = int(input())
for case in range(num_cases):
	length = int(input())
	string = input()
	print_combinations(list_combinations(list(string)))


import itertools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	S = sys.stdin.readline().strip()
	combinations = (itertools.combinations(S, n) for n in range(1, N + 1))
	for x in sorted(itertools.chain.from_iterable(combinations)):
		print(''.join(x))


def f(a, d, c, n):
	if d == n:
		return
	for x in c:
		if d > 0 and x <= a[d - 1]:
			continue
		a[d] = x
		print(''.join([a[i] for i in range(d + 1)]))
		f(a, d + 1, c, n)
for t in range(int(input())):
	n = int(input())
	s = input()
	a = list(' ' * n)
	f(a, 0, sorted(s), n)


from itertools import combinations
t = int(input())
while t != 0:
	L = []
	t -= 1
	n = int(input())
	a = input()
	for i in range(1, n + 1, 1):
		for p in combinations(a, i):
			L.append(''.join(p))
	x = sorted(list(set(L)))
	for i in x:
		print(i)


import fileinput
isString = True
for line in fileinput.input():
	if fileinput.isfirstline():
		continue
	else:
		isString = not isString
		if not isString:
			continue
		word = line.rstrip()
		l = []
		for bitmask in range(1, 2 ** len(word)):
			s = ''
			for y in range(0, len(word)):
				if bitmask >> y & 1:
					s += word[y]
			l += [s]
		for s in sorted(l):
			print(s)


__author__ = 'Shivani'

def print_str(l, s, j, ans):
	print(s)
	ans.append(s)
	for x in range(j, len(l)):
		temp = s + l[x]
		print_str(l, temp, x + 1, ans)

def chan(l):
	l = sorted(l)
	ans = []
	for i in range(len(l)):
		s = l[i]
		print_str(l, s, i + 1, ans)

def main():
	for i in range(int(input())):
		n = int(input())
		chan(list(input()))
main()


def substrings(chars):
	if len(chars) == 0:
		return
	yield chars[0]
	for substring in substrings(chars[1:]):
		yield (chars[0] + substring)
	for substring in substrings(chars[1:]):
		yield substring
T = int(input())
for _ in range(T):
	N = int(input())
	string = list(input())
	string.sort()
	for substring in substrings(string):
		print(substring)


import itertools
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	ans = []
	for i in range(1, n + 1):
		for j in list(itertools.combinations(s, i)):
			ans.append(''.join(j))
	ans.sort()
	for k in ans:
		print(k)


from itertools import combinations
testcases = int(input().strip())
for case in range(testcases):
	n = int(input().strip())
	s = input().strip()
	outputlist = []
	for length in range(len(s)):
		outputlist.extend([''.join(combo) for combo in combinations(s, length + 1)])
	outputlist.sort()
	for out in outputlist:
		print(out)


__author__ = 'vikas'
t = int(input())

def prints(s, i):
	start = i
	n = len(s)
	if i >= n:
		return
	while start < n:
		print(s[i:start + 1], sep='', end='\n')
		start = start + 1
	prints(s, i + 1)

def combination(s, x, l, i):
	if i >= len(s):
		l.append(x)
		return
	combination(s, x, l, i + 1)
	x = x + s[i:i + 1]
	combination(s, x, l, i + 1)
while t:
	l = int(input())
	s = input()
	l = []
	x = ''
	combination(s, x, l, 0)
	l.sort()
	l = l[1:]
	for i in l:
		print(i)
	t = t - 1