You are given a string S of length N.

You can apply the following operation on the string any number of times:
Choose an index i (1≤ i < N), and swap S_{i} with S_{i+1}, if S_{i} and S_{i+1} contain adjacent characters.  
For example, a and b are adjacent, z and y are adjacent, x and y are adjacent, while c and e are not adjacent. Note that a and z are not considered adjacent.

Find the lexicographically smallest string you can obtain, by applying the above operation any number of times.

Note: String X is lexicographically smaller than string Y if X_{i} < Y_{i}, where i is the first index where X and Y differ.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of the string.
- The second line contains the string S, consisting of lowercase english alphabets. 

------ Output Format ------ 

For each test case, output on a new line - the lexicographically smallest string that we can obtain from the given string using any number of operations.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$S$ consists of lowercase english alphabets only.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
2
5
cbaba
6
dbbced
----- Sample Output 1 ------ 
bbcaa
cdbbde
----- explanation 1 ------ 
Test case $1$: For the given string cbaba:
   
- We swap c and b at indices $1$ and $2$ and the string becomes: bcaba.
- Swap a and b at indices $3$ and $4$ and the string becomes: bcbaa.
- Finally swap c and b at indices $2$ and $3$ and the string becomes: bbcaa.

Note that this is the lexicographically smallest string we can obtain using any number of operations.

Test case $2$: For the given string dbbced:
   
- We swap b and c at indices $3$ and $4$ and the string becomes: dbcbed.
- Swap b and c at indices $2$ and $3$ and the string becomes: dcbbed.
- Swap d and c at indices $1$ and $2$ and the string becomes: cdbbed.
- Finally swap e and d at indices $5$ and $6$ and the string becomes: cdbbde.

Note that this is the lexicographically smallest string we can obtain using any number of operations.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Directed graphs

Greedy algorithms


Solutions:
from heapq import heapify, heappush, heappop

def solve():
	n = int(input())
	text = [x - 97 for x in map(ord, input().strip())]
	graph = [[] for _ in range(n)]
	pos = [[] for _ in range(26)]
	for i in range(n - 1, -1, -1):
		pos[text[i]].append(i)
	heap = []
	in_degree = [0] * n
	for (x, neighbors) in zip(text, graph):
		i = pos[x].pop()
		if in_degree[i] == 0:
			heap.append((x, i))
		for (y, p) in enumerate(pos):
			if p and abs(x - y) != 1:
				j = p[-1]
				neighbors.append(j)
				in_degree[j] += 1
	heapify(heap)
	out = []
	while heap:
		(x, i) = heappop(heap)
		out.append(x + 97)
		for j in graph[i]:
			in_degree[j] -= 1
			if in_degree[j] == 0:
				heappush(heap, (text[j], j))
	print(''.join(map(chr, out)))

def main():
	n_cases = int(input())
	for _ in range(n_cases):
		solve()
main()


from sys import stdin, stdout
from heapq import heapify, heappush, heappop
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input().split()))

def solve():
	n = r_int()
	text = [x - 97 for x in map(ord, input().strip())]
	graph = [[] for _ in range(n)]
	pos = [[] for _ in range(26)]
	for i in range(n - 1, -1, -1):
		pos[text[i]].append(i)
	heap = []
	in_degree = [0] * n
	for (x, neighbors) in zip(text, graph):
		i = pos[x].pop()
		if in_degree[i] == 0:
			heap.append((x, i))
		for (y, p) in enumerate(pos):
			if p and abs(x - y) != 1:
				j = p[-1]
				neighbors.append(j)
				in_degree[j] += 1
	heapify(heap)
	out = []
	while heap:
		(x, i) = heappop(heap)
		out.append(x + 97)
		for j in graph[i]:
			in_degree[j] -= 1
			if in_degree[j] == 0:
				heappush(heap, (text[j], j))
	print(''.join(map(chr, out)))

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()