You are given a permutation of length $n$. Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not a permutation ($2$ appears twice in the array) and $[1, 3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

You can perform at most $n-1$ operations with the given permutation (it is possible that you don't perform any operations at all). The $i$-th operation allows you to swap elements of the given permutation on positions $i$ and $i+1$. Each operation can be performed at most once. The operations can be performed in arbitrary order.

Your task is to find the lexicographically minimum possible permutation obtained by performing some of the given operations in some order.

You can see the definition of the lexicographical order in the notes section.

You have to answer $q$ independent test cases.

For example, let's consider the permutation $[5, 4, 1, 3, 2]$. The minimum possible permutation we can obtain is $[1, 5, 2, 4, 3]$ and we can do it in the following way:

  perform the second operation (swap the second and the third elements) and obtain the permutation $[5, 1, 4, 3, 2]$;  perform the fourth operation (swap the fourth and the fifth elements) and obtain the permutation $[5, 1, 4, 2, 3]$;  perform the third operation (swap the third and the fourth elements) and obtain the permutation $[5, 1, 2, 4, 3]$.  perform the first operation (swap the first and the second elements) and obtain the permutation $[1, 5, 2, 4, 3]$; 

Another example is $[1, 2, 4, 3]$. The minimum possible permutation we can obtain is $[1, 2, 3, 4]$ by performing the third operation (swap the third and the fourth elements).


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 100$) — the number of test cases. Then $q$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 100$) — the number of elements in the permutation.

The second line of the test case contains $n$ distinct integers from $1$ to $n$ — the given permutation.


-----Output-----

For each test case, print the answer on it — the lexicograhically minimum possible permutation obtained by performing some of the given operations in some order.


-----Example-----
Input
4
5
5 4 1 3 2
4
1 2 4 3
1
1
4
4 3 2 1

Output
1 5 2 4 3 
1 2 3 4 
1 
1 4 3 2 



-----Note-----

Recall that the permutation $p$ of length $n$ is lexicographically less than the permutation $q$ of length $n$ if there is such index $i \le n$ that for all $j$ from $1$ to $i - 1$ the condition $p_j = q_j$ is satisfied, and $p_i < q_i$. For example:

  $p = [1, 3, 5, 2, 4]$ is less than $q = [1, 3, 5, 4, 2]$ (such $i=4$ exists, that $p_i < q_i$ and for each $j < i$ holds $p_j = q_j$),  $p = [1, 2]$ is less than $q = [2, 1]$ (such $i=1$ exists, that $p_i < q_i$ and for each $j < i$ holds $p_j = q_j$).

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms


Solutions:
q = int(input())
for w in range(q):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	flag = [False for i in range(n - 1)]
	k = -1
	while k < n - 1:
		arr1 = arr[k + 1:]
		m = min(arr1)
		k1 = arr.index(m)
		if k1 != k + 1:
			for j in range(k1, k + 1, -1):
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
				flag[j - 1] = True
			k = k1
		else:
			k += 1
	for i in range(n - 1):
		if not flag[i]:
			if arr[i] > arr[i + 1]:
				flag[i] = True
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	print(*arr)


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	visited = [0] * n
	index = [0] * (n + 1)
	for i in range(1, n + 1):
		index[i] = arr.index(i)
	for i in range(1, n + 1):
		for j in range(index[i], 0, -1):
			if visited[j] == 0 and arr[j - 1] > arr[j]:
				temp = arr[j]
				arr[j] = arr[j - 1]
				arr[j - 1] = temp
				visited[j] += 1
	for i in arr:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	(*a,) = map(int, input().split())
	(ans, i) = ([], 0)
	while a:
		m = min(a)
		x = a.index(m)
		ans.append(m)
		if x == 0:
			a.remove(m)
			continue
		ans += a[:x - 1]
		a = a[x - 1:]
		if m in a:
			a.remove(m)
	print(*ans)


from sys import stdin, stdout
from collections import defaultdict
import heapq
import math

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

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

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

def get_string():
	return stdin.readline().strip()
INF = 10000000000.0
mod = 1000000000.0 + 7
for _ in range(int(stdin.readline())):
	n = get_int()
	a = get_array()
	vis = []
	max_d = -INF
	idx = -1
	f = 0
	for i in range(n - 1):
		f = 0
		for j in range(n - 1):
			if a[j] < a[j + 1]:
				continue
			if a[j] - a[j + 1] > max_d:
				if j not in vis:
					f = 1
					idx = j
		if f == 1:
			(a[idx], a[idx + 1]) = (a[idx + 1], a[idx])
			vis.append(idx)
	for i in a:
		print(i, end=' ')
	print()


I = input
for _ in [0] * int(I()):
	I()
	a = [*map(int, I().split())]
	i = 0
	while a[i:]:
		j = a.index(min(a[i:]))
		a[i:i] = (a.pop(j),)
		i = j + (j == i)
	print(*a)


def solve(a):
	if not a:
		return []
	i = a.index(min(a))
	if not i:
		return [a[0]] + solve(a[1:])
	head = [a[i]] + a[:i - 1]
	rest = [a[i - 1]] + a[i + 1:]
	return head + solve(rest)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(*solve(a))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = []
	for i in range(n - 1, 0, -1):
		if l[i] < l[i - 1]:
			k = l[i]
			l[i] = l[i - 1]
			l[i - 1] = k
		else:
			c.append(i - 1)
	c.sort()
	for i in range(len(c)):
		if l[c[i]] > l[c[i] + 1]:
			k = l[c[i]]
			l[c[i]] = l[c[i] + 1]
			l[c[i] + 1] = k
	print(*l)


try:
	from sys import stdin
	t = int(stdin.readline())
	for z in range(t):
		n = int(stdin.readline())
		a = list(map(int, input().split()))
		v = [0] * n
		for i in range(1, n + 1):
			x = a.index(i)
			while x - 1 >= 0 and a[x - 1] > i and (v[x - 1] == 0):
				(a[x], a[x - 1]) = (a[x - 1], a[x])
				v[x - 1] = 1
				x -= 1
		print(*a)
except:
	pass


import sys
from collections import Counter

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
for _ in range(INT()):
	N = INT()
	A = [a - 1 for a in LIST()]
	atoi = {}
	for (i, a) in enumerate(A):
		atoi[a] = i
	used = [0] * N
	for a in range(N):
		i = atoi[a]
		j = i
		while j > 0 and A[j - 1] > A[j] and (not used[j]):
			(A[j], A[j - 1]) = (A[j - 1], A[j])
			atoi[A[j]] += 1
			used[j] = 1
			j -= 1
		atoi[A[j]] = j
	print(*[a + 1 for a in A])


t = int(input())

def mnp(a, l, r):
	res = -1
	for i in range(l, r + 1):
		if res == -1 or a[i] < a[res]:
			res = i
	return res
while t:
	n = int(input())
	a = [0] + list(map(int, input().split()))
	p = [0 for i in range(0, n + 1)]
	ans = []
	last = 1
	while last <= n:
		p = mnp(a, last, n)
		if p == last:
			ans.append(a[p])
			last += 1
		else:
			ans.append(a[p])
			for i in range(last, p - 1):
				ans.append(a[i])
			a[p] = a[p - 1]
			last = p
	for i in ans:
		print(i, end=' ')
	print()
	t -= 1


n = int(input())
for i in range(n):
	l = int(input())
	a = list(map(int, input().split()))
	top = 0
	cnt = 0
	while top < l - 1:
		idx = a.index(min(a[top:]))
		if top == idx:
			top += 1
			continue
		a.insert(top, a.pop(idx))
		top = idx
	print(*a)


q = int(input())
for __ in [0] * q:
	n = int(input())
	a = list(map(int, input().split()))
	idx = [-1] * (n + 1)
	for (i, e) in enumerate(a):
		idx[e] = i
	res = []
	k = -1
	for (i, e) in enumerate(idx):
		if e == -1:
			continue
		if e > k:
			res.append(i)
			if i != 1:
				if res[-1] < res[-2]:
					(res[-1], res[-2]) = (res[-2], res[-1])
			for i in range(k + 1, e):
				res.append(a[i])
			k = e
	for e in res:
		if e != res[-1]:
			print(e, end=' ')
		else:
			print(e)


for _ in range(int(input())):
	n = int(input())
	check = [i for i in range(n)]
	A = list(map(int, input().split()))
	count = True
	while count:
		count = False
		for i in range(n):
			x = A.index(i + 1)
			while x != 0 and x in check and (A[x - 1] > A[x]):
				count = True
				(A[x], A[x - 1]) = (A[x - 1], A[x])
				check.remove(x)
				x -= 1
	for i in range(n - 1):
		print(A[i], end=' ')
	print(A[-1])


q = int(input())
for w in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	p = [0 for i in range(n)]
	u = sorted(l)
	ch = 1
	while ch > 0 and 0 in p:
		ch = 0
		for i in range(n - 1, 0, -1):
			if p[i] == 0:
				if l[i - 1] > l[i]:
					(l[i], l[i - 1]) = (l[i - 1], l[i])
					p[i] = 1
					ch += 1
	for i in l:
		print(i, end=' ')
	print()


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	posis = [-1] * (n + 1)
	fixedi = -1
	for i in range(n):
		d = p[i]
		posis[d] = i
	for i in range(1, n + 1):
		if posis[i] == fixedi + 1:
			fixedi += 1
			continue
		posi = posis[i]
		if posi > fixedi:
			j = posi
			while j > fixedi + 1:
				p[j] = p[j - 1]
				posis[p[j]] = j
				j -= 1
			p[j] = i
			posis[i] = j
			fixedi = posi - 1
	print(' '.join(list(map(str, p))))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	l = 0
	while l < n - 1:
		r = ar.index(min(ar[l:]))
		for i in range(r, l, -1):
			xx = ar[i]
			ar[i] = ar[i - 1]
			ar[i - 1] = xx
		l = max(r, l + 1)
	print(*ar)


def func(last, ind, visited, places):
	while last < n and ind <= n:
		cur = places[ind]
		if cur != ind:
			if visited[cur - 1] == False:
				if arr[cur - 1] > ind:
					visited[cur - 1] = True
					places[ind] = cur - 1
					places[arr[cur - 1]] = cur
					temp = arr[cur - 1]
					arr[cur - 1] = ind
					arr[cur] = temp
					last += 1
				else:
					ind += 1
			else:
				ind += 1
		else:
			ind += 1
	return arr[1:]
for _ in range(int(input())):
	n = int(input())
	(last, ind) = (1, 1)
	arr = list(map(int, input().split()))
	arr = [-1] + arr
	visited = [False for i in range(n + 1)]
	places = {}
	for i in range(n + 1):
		places[arr[i]] = i
	arr = func(last, ind, visited, places)
	print(*arr)


IN = lambda : list(map(int, input().split()))

def move_front(arr, idx, start):
	e = arr[idx]
	while idx > start:
		arr[idx] = arr[idx - 1]
		idx -= 1
	arr[start] = e

def arrange(arr, start, min_idx_arr):
	if start == len(arr) - 1:
		return
	min_idx = start
	if arr[min_idx] > arr[min_idx_arr[start + 1]]:
		min_idx = min_idx_arr[start + 1]
	if min_idx == start:
		arrange(arr, start + 1, min_idx_arr)
	else:
		move_front(arr, min_idx, start)
		arrange(arr, min_idx, min_idx_arr)
q = int(input())
for _ in range(q):
	n = int(input())
	arr = IN()
	min_idx_arr = [0 for _ in range(n)]
	min_idx_arr[n - 1] = n - 1
	for i in range(n - 2, -1, -1):
		if arr[i] < arr[min_idx_arr[i + 1]]:
			min_idx_arr[i] = i
		else:
			min_idx_arr[i] = min_idx_arr[i + 1]
	arrange(arr, 0, min_idx_arr)
	print(' '.join([str(e) for e in arr]))


test = int(input(''))
for _ in range(test):
	n = int(input())
	lstin = [int(x) for x in input().split()]
	visited = [False] * (n - 1)
	for i in range(n):
		if lstin[i] == 1:
			pos1 = i
			break
	lstin.remove(1)
	lstin.insert(0, 1)
	visited[:pos1] = [True] * pos1
	j = 2
	index = pos1
	while j < n and index < n - 1:
		for i in range(n):
			if lstin[i] == j:
				pos = i
				break
		if visited[pos - 1]:
			j += 1
			continue
		else:
			i = pos - 1
			while visited[i] == False and lstin[i] > j:
				visited[i] = True
				i -= 1
			lstin.remove(j)
			lstin.insert(i + 1, j)
			index = pos
			j += 1
	print(*lstin)


import sys, atexit
from io import BytesIO
inp = BytesIO(sys.stdin.buffer.read())
input = lambda : inp.readline().decode('ascii')
buf = BytesIO()
atexit.register(lambda : sys.__stdout__.buffer.write(buf.getvalue()))
for i in range(int(input())):
	n = int(input())
	a = [1000000] + list(map(int, input().split()))
	s = set()
	i = 1
	for i in range(1, n + 1):
		x = a.index(i)
		while x > 0 and a[x] < a[x - 1] and (x not in s):
			(a[x], a[x - 1]) = (a[x - 1], a[x])
			s.add(x)
			x -= 1
	for i in a:
		if i > 100:
			continue
		print(i, end=' ')
	print()


I = input
for _ in [0] * int(I()):
	I()
	a = [*map(int, I().split())]
	i = k = 0
	while k < len(a):
		k += 1
		j = a.index(k)
		if j >= i:
			a.insert(i, a.pop(j))
			i = j + (i == j)
	print(*a)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
mod = int(1000000000.0) + 7
mod = 998244353
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	arr = list(inp())
	val = n - 1
	i = 0
	mark = [False] * n
	while i < n:
		ch = min(arr[i:])
		pos = arr.index(ch)
		if pos == i:
			pass
		else:
			for j in range(pos, i, -1):
				if val == 0:
					break
				elif mark[j - 1]:
					break
				else:
					(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
					val -= 1
					mark[j - 1] = True
		i += 1
	print(*arr)


q = int(input())
for _ in range(q):
	n = int(input())
	p = [int(t) for t in input().split(' ')]
	lindex = 0
	for i in range(1, n + 1):
		index = p.index(i)
		i = index
		while i > lindex:
			if p[i] > p[i - 1]:
				break
			(p[i], p[i - 1]) = (p[i - 1], p[i])
			i -= 1
		lindex = max(lindex, index)
	print(*p)


import sys

def solve(list_num):
	if len(list_num) <= 1:
		return list_num
	i = min(range(len(list_num)), key=lambda x: list_num[x])
	return [list_num[i]] + list_num[:max(i - 1, 0)] + solve(([] if i == 0 else [list_num[i - 1]]) + list_num[i + 1:])
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	list_num = list(map(int, sys.stdin.readline().split()))
	print(*solve(list_num))


def doit(lst):
	n = len(lst)
	if n <= 1:
		return lst
	index = lst.index(min(lst))
	if index == 0:
		l = doit(lst[1:])
		return [lst[0]] + l
	temp = [lst[index - 1]] + lst[index + 1:]
	return [lst[index]] + lst[:index - 1] + doit(temp)
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(*doit(lst))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	swap = 0
	swapped = True
	while swap < n:
		swapped = False
		mi = -1
		m = n + 1
		for i in range(swap, n):
			if a[i] < m:
				m = a[i]
				mi = i
		b = a.copy()
		b[swap] = m
		for j in range(swap + 1, mi + 1):
			swapped = True
			b[j] = a[j - 1]
		swap = mi if swapped else swap + 1
		a = b
	print(' '.join(map(str, a)))


t = int(input())
for i in range(t):
	n = int(input())
	temp = 0
	b = [0 for i in range(n)]
	l = list(map(int, input().split(' ')))
	a = l[::-1]
	for i in range(n - 1):
		if a[i] < a[i + 1]:
			temp = a[i]
			a[i] = a[i + 1]
			a[i + 1] = temp
			b[i + 1] = 1
	a = a[::-1]
	b = b[::-1]
	for i in range(n - 1):
		if b[i] == 0:
			if a[i] > a[i + 1]:
				temp = a[i]
				a[i] = a[i + 1]
				a[i + 1] = temp
				b[i] = 1
	c = a
	for i in c:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	swapped = [False] * (int(input()) - 1)
	x = [int(x) for x in input().split()]
	while False in swapped and (not sorted(x) == x):
		change = False
		for cur in range(len(x) - 2, -1, -1):
			if x[cur] > x[cur + 1] and (not swapped[cur]):
				(x[cur], x[cur + 1]) = (x[cur + 1], x[cur])
				swapped[cur] = True
				change = True
		if not change:
			break
	print(' '.join([str(i) for i in x]))


def func(arr):
	index = arr.index(min(arr))
	if len(arr) == 1:
		return arr
	elif index == 0:
		return [arr[index]] + func(arr[index + 1:])
	elif len(arr) != index + 1:
		return [arr[index]] + arr[:index - 1] + func([arr[index - 1]] + arr[index + 1:])
	else:
		return [arr[index]] + arr[:index]
for iter in range(int(input())):
	n = int(input())
	mass = list(map(int, input().split()))
	print(*func(mass))


import sys
input = sys.stdin.readline
y = int(input())
for i in range(y):
	n = int(input())
	arr = list(map(int, input().split()))
	a = 0
	visited = [0] * n
	for j in range(n):
		for k in range(n - 1, 0, -1):
			if visited[k - 1] == 0 and arr[k - 1] > arr[k]:
				visited[k - 1] = 1
				temp = arr[k - 1]
				arr[k - 1] = arr[k]
				arr[k] = temp
	s = ''
	for j in arr:
		s = s + str(j) + ' '
	s = s[:-1]
	print(s)


def ii():
	return int(input())

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

def mp():
	return map(int, input().split())

def i():
	return input()
for _ in range(ii()):
	n = ii()
	a = li()
	c = set()
	f = 0
	for i in range(1, n + 1):
		for j in range(n):
			if a[j] == i:
				f = 1
				for k in range(j, i - 1, -1):
					if k - 1 in c:
						break
					if a[k] < a[k - 1]:
						(a[k], a[k - 1]) = (a[k - 1], a[k])
						c.add(k - 1)
			if f == 1:
				f = 0
				break
	print(*a)


q = int(input())
for i in range(q):
	w = int(input())
	e = list(map(int, input().split()))
	r = [1] * w
	for k in range(1, w + 1):
		t = e.index(k)
		while t > 0 and r[t - 1] and (e[t] < e[t - 1]):
			if r[t - 1]:
				(e[t - 1], e[t]) = (e[t], e[t - 1])
				r[t - 1] = 0
			t -= 1
	print(*e)


for _ in range(int(input())):
	input()
	A = list(map(int, input().split()))
	p_x = 0
	while p_x < len(A) - 1:
		r_neigh = A[p_x:]
		y = min(r_neigh)
		if A[p_x] > y:
			A.remove(y)
			A.insert(p_x, y)
			p_x += r_neigh.index(y)
		else:
			p_x += 1
	print(*A)


def main(length, sequence):
	max_swaps = length - 1
	order_to_check = sorted(sequence)
	swaps = 0
	order_idx = 0
	swaps_done = []
	while swaps != max_swaps and sequence != order_to_check:
		if order_idx == length:
			break
		curr_idx = sequence.index(order_to_check[order_idx])
		while True:
			if curr_idx - 1 < 0:
				break
			swap = str(curr_idx) + str(curr_idx - 1)
			if swap in swaps_done:
				break
			curr_number = sequence[curr_idx]
			prev_number = sequence[curr_idx - 1]
			if prev_number > curr_number:
				sequence[curr_idx] = prev_number
				sequence[curr_idx - 1] = curr_number
				swaps += 1
				swaps_done.append(swap)
			curr_idx -= 1
		order_idx += 1
	print(' '.join(map(str, sequence)))
test_cases = int(input())
for i in range(test_cases):
	length = int(input())
	sequence = [int(num) for num in input().split()]
	main(length, sequence)


def combination_min(n, s):
	ans = []
	while s:
		idx = s.index(min(s))
		ans.append(s[idx])
		if idx != 0:
			ans.extend(s[:idx - 1])
			s[idx] = s[idx - 1]
			s = s[idx:]
		else:
			s = s[idx + 1:]
	return ' '.join([str(i) for i in ans])
q = int(input())
for i in range(q):
	n = int(input())
	s = list(map(int, input().split()))
	print(combination_min(n, s))


import sys, os, io

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

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

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

def ws(s):
	sys.stdout.write(s + '\n')

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

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect
from collections import deque, defaultdict, OrderedDict
import collections

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(ri()):
		n = ri()
		a = ria()
		d = {}
		for i in range(1, n):
			for j in range(n):
				if a[j] == i:
					k = j - i + 1
					for h in range(k):
						if j - h - 1 not in d and a[j - h - 1] > a[j - h]:
							d[j - h - 1] = 1
							(a[j - h], a[j - h - 1]) = (a[j - h - 1], a[j - h])
						else:
							break
					break
		print(*a)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


q = int(input())
for t in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	used = [0] * n
	for i in range(1, n + 1):
		ind = a.index(i)
		while ind > 0 and used[ind - 1] == 0 and (a[ind - 1] > i):
			s = a[ind - 1]
			a[ind] = s
			a[ind - 1] = i
			used[ind - 1] = 1
			ind -= 1
	print(*a)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def findmin(cv, vals, moves):
	minsofar = vals[cv]
	key = cv
	for s in range(cv + 1, min(len(vals), cv + 1 + moves)):
		if vals[s] < minsofar:
			minsofar = vals[s]
			key = s
	return key
testcases = int(input())
for j in range(testcases):
	n = int(input())
	vals = list(map(int, input().split()))
	cv = 0
	moves = n - 1
	while cv < n - 1 and moves > 0:
		ind = findmin(cv, vals, n - 1)
		for s in range(ind, cv, -1):
			(vals[s], vals[s - 1]) = (vals[s - 1], vals[s])
			moves -= 1
		if ind != cv:
			cv = ind
		else:
			cv += 1
	print(*vals)


q = int(input())
for tc in range(q):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	nw = 0
	while nw < n:
		mi = min(arr[nw:])
		pl = arr.index(mi)
		arr = arr[:nw] + [arr[pl]] + arr[nw:pl] + arr[pl + 1:]
		if nw == pl:
			nw += 1
		else:
			nw = pl
	print(*arr)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(1, n + 1):
		d[i] = True
	t = 1
	g = 0
	for i in range(n):
		if a[i] == t:
			d[a[i]] = False
			if a[i] != i + 1:
				for j in range(i, g, -1):
					if a[j] < a[j - 1]:
						f = a[j - 1]
						a[j - 1] = a[j]
						a[j] = f
						d[a[j]] = False
						d[a[j - 1]] = False
					else:
						break
			g = i
			for j in d:
				if d[j] == True:
					t = j
					break
	print(*a)


q = int(input())
for j in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	t = 1
	ind = 0
	u = []
	for i in range(n - 1):
		ind = a.index(t)
		if ind == 0:
			t += 1
			ind = a.index(t)
		while ind in u:
			t += 1
			if t > n:
				break
			ind = a.index(t)
		u.append(ind)
		if a[ind - 1] > a[ind]:
			(a[ind - 1], a[ind]) = (a[ind], a[ind - 1])
	print(' '.join(list(map(str, a))))


n = int(input())
for _ in range(n):
	k = int(input())
	numbers = list(map(int, input().split(' ')))
	what = [True for i in range(k)]
	for i in range(1, k + 1):
		while True:
			index = numbers.index(i)
			if i == index + 1:
				break
			elif index + 1 < i and what[index] and (numbers[index + 1] < numbers[index]):
				what[index] = False
				(numbers[index], numbers[index + 1]) = (numbers[index + 1], numbers[index])
			elif index + 1 > i and what[index - 1] and (numbers[index - 1] > numbers[index]):
				what[index - 1] = False
				(numbers[index], numbers[index - 1]) = (numbers[index - 1], numbers[index])
			else:
				break
	print(' '.join(map(str, numbers)))


q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	s = []
	l = l[::-1]
	pred = 0
	for j in range(n - 1):
		if l[j] < l[j + 1]:
			(l[j], l[j + 1]) = (l[j + 1], l[j])
			pred += 1
		else:
			s.append(j)
	while len(s) > 0:
		if pred > 0:
			pred = 0
			for j in s:
				if l[j] < l[j + 1]:
					(l[j], l[j + 1]) = (l[j + 1], l[j])
					pred += 1
					s.pop(s.index(j))
		else:
			break
	print(*l[::-1])


def f(a, l):
	m = a[l]
	mi = l
	for i in range(l, len(a)):
		if a[i] < m:
			m = a[i]
			mi = i
	for i in range(mi, l, -1):
		a[i] = a[i - 1]
	a[l] = m
	return mi if mi != l else mi + 1
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	mi = 0
	while mi < n:
		mi = f(a, mi)
	print(*a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = n - 1
	done = [0] * (n - 1)
	i = n - 2
	while i >= 0 and cnt:
		for j in range(i, n - 1):
			if a[j] > a[j + 1] and done[j] == 0:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
				done[j] = 1
				cnt -= 1
		i -= 1
	print(*a)


def optimize(arr, idx):
	if idx >= len(arr):
		return
	min_idx = -1
	min_val = 1000000000.0
	for i in range(idx, len(arr)):
		if arr[i] < min_val:
			min_val = arr[i]
			min_idx = i
	for i in range(min_idx - 1, idx - 1, -1):
		tmp = arr[i]
		arr[i] = arr[i + 1]
		arr[i + 1] = tmp
	if min_idx == idx:
		min_idx += 1
	optimize(arr, min_idx)
q = int(input())
for t in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	optimize(a, 0)
	print(*a)


T = int(input())
for ii in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	d = []
	k = 0
	for i in range(1, n + 1):
		idx = arr.index(i)
		if idx == k:
			k += 1
			continue
		if idx > k:
			j = idx
			arr = arr[:k] + [arr[j]] + arr[k:j] + arr[j + 1:]
			k = j
	print(*arr)


q = int(input())
ans = []
for j in range(q):
	n = int(input())
	mass = list(map(int, input().split(' ')))
	mass = mass[::-1]
	p = [0 for i in range(n - 1)]
	ind = 1
	while ind == 1:
		ind = 0
		for i in range(n - 1):
			if p[i] == 0:
				if mass[i] < mass[i + 1]:
					p[i] = 1
					(mass[i], mass[i + 1]) = (mass[i + 1], mass[i])
					ind = 1
	mass = mass[::-1]
	mass = ' '.join([str(i) for i in mass])
	ans.append(mass)
for j in range(q):
	print(ans[j])


q = int(input())
for _ in range(q):
	n = int(input())
	tmp = list(map(int, input().split()))
	j = 0
	while True:
		l = j
		mi = n + 1
		for i in range(j, n):
			if mi > tmp[i]:
				mi = tmp[i]
				j = i
		if j == l:
			j += 1
		else:
			for i in range(j, l, -1):
				tmp[i] = tmp[i - 1]
			tmp[l] = mi
		if j >= n - 1:
			break
	print(*tmp)


for i in range(int(input())):
	n = int(input())
	arr = map(int, input().split())
	arr = list(arr)
	s = set()
	for j in range(n):
		for i in range(n - 1, 0, -1):
			if arr[i] < arr[i - 1] and i not in s:
				s.add(i)
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
	arr = map(str, arr)
	print(' '.join(arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = [(i, i + 1) for i in range(n - 1)]
	d = sorted((i + 1 for i in range(n) if a[i] - 1 != i))
	l = len(d)
	ce = 0
	while x and ce < l:
		f = 0
		ind = a.index(d[ce])
		while (ind - 1, ind) in x and a[ind - 1] > a[ind]:
			(a[ind - 1], a[ind]) = (a[ind], a[ind - 1])
			x.remove((ind - 1, ind))
			ind -= 1
		ce += 1
	print(*a)


import sys

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = get_array()
		d = {}

		def solve(i):
			idx = 0
			for j in range(n):
				if arr[j] == i:
					idx = j
					break
			p = idx
			for j in range(idx - 1, -1, -1):
				if p in d:
					break
				if arr[j] < arr[p]:
					break
				(arr[p], arr[j]) = (arr[j], arr[p])
				d[p] = 1
				p -= 1
		for i in range(1, n + 1):
			solve(i)
		print(*arr)
input = lambda : sys.stdin.readline().strip()
get_ints = lambda : list(map(int, input().split()))
get_array = lambda : list(map(int, input().split()))
main()


from collections import Counter
import math
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def listt():
	return [int(i) for i in input().split()]

def gcd(a, b):
	return math.gcd(a, b)

def lcm(a, b):
	return a * b // gcd(a, b)

def factors(n):
	step = 2 if n % 2 else 1
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(math.sqrt(n)) + 1, step) if n % i == 0)))

def comb(n, k):
	factn = math.factorial(n)
	factk = math.factorial(k)
	fact = math.factorial(n - k)
	ans = factn // (factk * fact)
	return ans

def is_prime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	if n > 2 and n % 2 == 0:
		return False
	max_div = math.floor(math.sqrt(n))
	for i in range(3, 1 + max_div, 2):
		if n % i == 0:
			return False
	return True

def maxpower(n, x):
	B_max = int(math.log(n, x)) + 1
	return B_max

def binaryToDecimal(n):
	return int(n, 2)
t = int(input())
for _ in range(t):
	res = []
	n = int(input())
	a = listt()
	l = 0
	for m in range(1, n + 1):
		i = a.index(m)
		if i <= l:
			continue
		for j in range(i - 1, l - 1, -1):
			if a[j] < a[j + 1]:
				break
			(a[j], a[j + 1]) = (a[j + 1], a[j])
		l = i
	res.append(' '.join(map(str, a)))
	print(*res)


q = int(input())
while q:
	n = int(input())
	x = [int(_) for _ in input().split()]
	answer = []
	while len(x) > 1:
		min_pos = 0
		for i in range(1, len(x)):
			if x[i] < x[min_pos]:
				min_pos = i
		if min_pos == 0:
			answer.append(x[0])
			x = x[1:]
		else:
			answer += [x[min_pos]] + x[:min_pos - 1]
			x = [x[min_pos - 1]] + x[min_pos + 1:]
	answer += x
	print(*answer)
	q -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	s = sorted(l)
	h = set()
	while c != n - 1 and s:
		k = s.pop(0)
		idx = l.index(k)
		while idx > 0 and c != n - 1 and (idx not in h):
			if l[idx - 1] > k:
				(l[idx - 1], l[idx]) = (l[idx], l[idx - 1])
				c += 1
				h.add(idx)
				idx -= 1
			else:
				break
	print(*l)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ptr = 0
	for i in range(1, n + 1):
		if ptr == n - 1:
			break
		ptrn = arr.index(i)
		if ptrn < ptr:
			continue
		arr.remove(i)
		arr.insert(ptr, i)
		if ptrn == ptr:
			ptrn += 1
		ptr = ptrn
	print(*arr)


n = int(input())
ss = []
for i in range(n):
	input()
	ss += [input()]
for i in range(n):
	s = list(map(int, ss[i].split(' ')))
	max_idx = -1
	for j in range(1, len(s) + 1):
		idx = s.index(j)
		if max_idx == idx - 1:
			max_idx = idx
		elif max_idx < idx:
			s.insert(max_idx + 1, s.pop(idx))
			max_idx = idx - 1
		else:
			continue
	print(' '.join(list(map(str, s))))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def solve(case):
	n = int(inp())
	a = lis()
	to = 0
	have = n - 1
	while have > 0 and to < n - 1:
		mini = min(a[to:])
		ind = a.index(mini)
		a.remove(mini)
		a.insert(to, mini)
		if ind == to:
			to = ind + 1
		else:
			to = ind
	print(' '.join((str(a[i]) for i in range(len(a)))))
testcase(int(inp()))


from fractions import gcd
from datetime import date, timedelta
from heapq import *
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		a = list(map(int, input().split()))
		d = defaultdict(int)
		for i in range(n):
			d[a[i]] = i
		now = 1
		st = d[now]
		t = 0
		swap = 0
		while swap < n - 1 and now < n:
			if d[now] > t and a[d[now] - 1] > a[d[now]]:
				index = d[now]
				left = a[index - 1]
				(a[index], a[index - 1]) = (a[index - 1], a[index])
				d[left] += 1
				d[now] -= 1
				swap += 1
			else:
				t = st
				now += 1
				while d[now] < st + 1 and now <= n:
					now += 1
				st = d[now]
		print(*a)
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	while i < n - 1:
		x = min(a[i:])
		j = a.index(x, i)
		if j == i:
			i += 1
		else:
			a[i:j + 1] = [x] + a[i:j]
			i = j
	print(*a)


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	while l < n - 1:
		idx = a.index(min(a[l:]), l)
		if idx == l:
			l = idx + 1
			continue
		mini = a[idx]
		a[l + 1:idx + 1] = a[l:idx]
		a[l] = mini
		l = idx
	print(' '.join(map(str, a)))


import random
from bisect import bisect_left, bisect_right
from typing import List
import collections
import bisect
import itertools
import functools
from fractions import gcd
import heapq
from math import ceil, sqrt, floor
from collections import defaultdict, deque
import collections
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(sorted(A))
	used = [False] * n
	for k in range(n):
		for i in range(1, n):
			if A[i] == B[k]:
				j = i - 1
				while j >= 0 and A[j] > A[j + 1] and (not used[j]):
					used[j] = True
					(A[j], A[j + 1]) = (A[j + 1], A[j])
					j -= 1
				break
	print(' '.join((str(v) for v in A)))


for __ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	x = 1
	i = ar.index(x)
	num = 0
	while x < n and i < n:
		if x != 1:
			while i < n > x and (i >= ar.index(x) or ar.index(x) == x - 1):
				x += 1
		if i < n:
			i = ar.index(x)
			for j in range(i, num, -1):
				if ar[j] < ar[j - 1]:
					(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
				else:
					break
			num = i
		x += 1
	print(*ar)


def minimization(n, lst):
	a = [False] * (n - 1)
	for i in range(n):
		j = lst.index(i + 1)
		while j > i and lst[j] < lst[j - 1] and (not a[j - 1]):
			a[j - 1] = True
			(lst[j], lst[j - 1]) = (lst[j - 1], lst[j])
			j -= 1
	return lst
for _ in range(int(input())):
	m = int(input())
	b = [int(x) for x in input().split()]
	print(*minimization(m, b))


from sys import *
from math import *
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	b = [0] * n
	for i in range(n - 1, 0, -1):
		if a[i] < a[i - 1]:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
			b[i - 1] = 1
		for j in range(i, n - 1):
			if a[j] > a[j + 1] and b[j] == 0:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
				b[j] = 1
			else:
				break
	print(*a)


def run_testcase():
	n = int(input())
	permutation = [int(x) for x in input().split()]
	swaps = n - 1
	current_index = 0
	left = 0
	while left < n - 1:
		(min_val, min_index) = min(((v, i) for (i, v) in enumerate(permutation[left:])))
		min_index += left
		if min_index == left:
			left += 1
			continue
		for i in reversed(range(left, min_index)):
			(permutation[i], permutation[i + 1]) = (permutation[i + 1], permutation[i])
		left = min_index
	print(*permutation, sep=' ')
testcase_count = int(input())
for i in range(testcase_count):
	run_testcase()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 1
	per = -1
	seen = [0] * n
	while i <= n:
		yy = a.index(i)
		j = yy - 1
		while j >= 0 and a[yy] < a[j] and (seen[j] == 0):
			(a[yy], a[j]) = (a[j], a[yy])
			seen[j] = 1
			yy -= 1
			j -= 1
		i += 1
	print(*a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = [i for i in range(n)]
	d = list(zip(a, l))
	d.sort(key=lambda x: x[0])
	dic = {}
	for i in d:
		dic[i[0]] = i[1]
	m = 0
	for i in dic:
		if dic[i] == m:
			m += 1
		elif dic[i] > m:
			(dic[i], m) = (m, dic[i])
			if m - 1 >= 0 and a[m] != a[m - 1]:
				dic[a[m - 1]] += 1
				a[m] = a[m - 1]
		else:
			dic[i] += 1
	ans = [0] * n
	for i in dic:
		ans[dic[i]] = i
	print(*ans)


def arr_inp():
	return [int(x) for x in input().split()]

def fill_arr(n):
	return [i for i in range(n)]

def swap(x, y):
	(x, y) = (y, x)
for i in range(int(input())):
	(n, arr) = (int(input()), arr_inp())
	visit = fill_arr(n + 1)
	for j in range(n):
		visit[arr[j]] = j
	(pre, point) = (0, 0)
	for j in range(1, n + 1):
		point = visit[j]
		if point < pre:
			continue
		for k in range(point, pre, -1):
			if j < arr[k - 1]:
				(arr[k], arr[k - 1]) = (arr[k - 1], arr[k])
			pre = point
	print(*arr)


import sys

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

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

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	N = int(input())
	A = alele()
	B = [0] * int(N)
	for mini in range(1, 101):
		i = 0
		while i < len(A) - 1:
			i += 1
			if A[i] == mini:
				if A[i - 1] > mini and B[i - 1] == 0:
					(A[i - 1], A[i]) = (A[i], A[i - 1])
					B[i - 1] = 1
					i = 0
	for i in A:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = [*map(int, input().split())]
	used = [False] * (n - 1)
	for i in range(n):
		j = l.index(i + 1)
		while j > i and l[j] < l[j - 1] and (not used[j - 1]):
			used[j - 1] = True
			(l[j], l[j - 1]) = (l[j - 1], l[j])
			j -= 1
	print(*l)


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	prev_mark = 0
	while True:
		m = 10 ** 18
		mark = None
		for i in range(prev_mark, n):
			if m > a[i]:
				m = a[i]
				mark = i
		for i in range(mark - 1, prev_mark - 1, -1):
			(a[i], a[i + 1]) = (a[i + 1], a[i])
		if mark == n - 1:
			break
		if mark == prev_mark:
			prev_mark = mark + 1
		else:
			prev_mark = mark
	print(*a)


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
for _ in range(ii()):
	(n, ls) = (ii(), [x - 1 for x in kk()])
	l2 = [0] * n
	ind = -1
	for (i, v) in enumerate(ls):
		l2[v] = i
	for i in range(n):
		if l2[i] > ind:
			tmp = l2[i]
			i2 = l2[i]
			while l2[i] > ind + 1:
				(ls[i2 - 1], ls[i2]) = (ls[i2], ls[i2 - 1])
				l2[ls[i2]] += 1
				l2[i] -= 1
				i2 -= 1
			ind = max(tmp - 1, i2)
	print(*[x + 1 for x in ls])


a = []
n = 0

def f(mask, ct):
	if mask == (1 << n) - 1 or ct == 0:
		return
	j = len(a) - 1
	while j > 0:
		if mask & 1 << j - 1 == 0 and a[j - 1] > a[j]:
			(a[j], a[j - 1]) = (a[j - 1], a[j])
			mask |= 1 << j - 1
		j -= 1
	f(mask, ct - 1)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f(0, n)
	print(*a)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	z = set()
	for i in range(n):
		j = a.index(i + 1) - 1
		for k in range(j, i - 1, -1):
			if a[k] < i + 1:
				break
			if k not in z:
				(a[k], a[k + 1]) = (a[k + 1], a[k])
				z.add(k)
			else:
				break
	print(*a)


n = int(input())
for i in range(n):
	y = int(input())
	list1 = [int(x) for x in input().split(' ')]
	c = 0
	while c < y - 1:
		z = list1.index(min(list1[c:]))
		if z == c:
			c += 1
		else:
			(list1[c], list1[c + 1:z + 1]) = (list1[z], list1[c:z])
			c = z
	list1 = [str(x) for x in list1]
	print(' '.join(list1))


def f(v):
	n = len(v)
	if n < 2:
		return v
	i = 0
	while i < n:
		if v[i] == 1:
			break
		else:
			i += 1
	new = [1]
	for j in range(i - 1):
		new.append(v[j])
	if i == n - 1:
		return new + [v[i - 1]]
	if i > 0:
		resta = [v[i - 1]]
	else:
		resta = []
	resta += v[i + 1:]
	mi = min(resta)
	for k in range(len(resta)):
		el = resta[k]
		el -= mi
		el += 1
		resta[k] = el
	fine = f(resta)
	for el in fine:
		new.append(el + mi - 1)
	return new
q = int(input())
for j in range(q):
	n = int(input())
	v = list(map(int, input().rstrip().split()))
	res = f(v)
	print(' '.join(map(str, res)))


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	index = dict()
	elem = dict()
	for curr in range(n):
		index[a[curr]] = curr
		elem[curr] = a[curr]
	used = set()
	for curr in range(1, n + 1):
		prev = -1
		if index[curr] > 0:
			prev = elem[index[curr] - 1]
		while index[curr] > 0 and prev > curr and (index[curr] - 1 not in used):
			used.add(index[curr] - 1)
			elem[index[prev]] = curr
			elem[index[curr]] = prev
			index[prev] += 1
			index[curr] -= 1
			if index[curr] > 0:
				prev = elem[index[curr] - 1]
	for curr in range(1, n + 1):
		a[index[curr]] = str(curr)
	print(' '.join(a))


q = int(input())
while q:
	n = int(input())
	p = list(map(int, input().split(' ')))
	used = [0] * n
	m = n
	while m > 1:
		i = n - 1
		swap = False
		while m > 1 and i > 0:
			if not used[i] and p[i - 1] > p[i]:
				(p[i - 1], p[i]) = (p[i], p[i - 1])
				used[i] = 1
				m -= 1
				if not swap:
					swap = True
			i -= 1
		if not swap:
			break
	print(' '.join(map(str, p)))
	q -= 1


t = int(input())
for z in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	slot = n - 1
	tmp = -1
	for i in range(n):
		if i < tmp:
			continue
		if slot == 0:
			break
		nn = min(a[i:i + slot + 1])
		pos = a.index(nn)
		tmp = pos
		a = a[:i] + [nn] + a[i:pos] + a[pos + 1:]
		slot -= pos - i
	for i in a:
		print(i, end=' ')
	print()


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[i] = 0
	p = [i for i in range(1, n + 1)]
	pos = []
	for i in range(len(p)):
		pos.append(a.index(p[i]))
	op = 0
	i = 0
	while i < len(pos):
		if op == n - 1:
			break
		l = pos[i]
		if d[l] == 0:
			if a[l] < a[l - 1] and l - 1 >= 0:
				(a[l - 1], a[l]) = (a[l], a[l - 1])
				d[l] += 1
				op += 1
				pos[pos.index(l - 1)] += 1
				pos[i] -= 1
				if pos[i] == 0:
					i += 1
			else:
				i += 1
		else:
			i += 1
	print(*a)


q = int(input())
for lol in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	A = set()
	for i in range(n - 1):
		A.add((i, i + 1))
	step = 0
	j = 1
	index_1 = 0
	while len(A) > 0 and j <= n:
		for i in range(n):
			if a[i] == j:
				index_1 = i
		for i in reversed(range(1, index_1 + 1)):
			if a[i - 1] > a[i]:
				if (i - 1, i) in A:
					c = a[i - 1]
					a[i - 1] = a[i]
					a[i] = c
					A.remove((i - 1, i))
		j += 1
	print(*a)


q = int(input())
for _ in range(q):
	n = int(input())
	P = list(map(int, input().split()))
	used = set()
	for i in reversed(range(1, n)):
		if P[i - 1] > P[i]:
			(P[i], P[i - 1]) = (P[i - 1], P[i])
			used.add((i - 1, i))
	for i in range(n - 1):
		if P[i] > P[i + 1] and (i, i + 1) not in used:
			(P[i], P[i + 1]) = (P[i + 1], P[i])
	print(*P)


T = int(input())
while T > 0:
	T -= 1
	n = int(input())
	vis = [False] * (n + 1)
	arr = [0] + list(map(int, input().strip().split(' ')))
	for i in range(1, n + 1):
		ind = arr.index(i, 1)
		while vis[ind] != True and ind >= 1 and (arr[ind] < arr[ind - 1]):
			(arr[ind], arr[ind - 1]) = (arr[ind - 1], arr[ind])
			vis[ind] = True
			ind -= 1
	for i in range(1, n + 1):
		print(arr[i], end=' ')
	print()


import copy

def min_sort(vals):
	vals = copy.deepcopy(vals)
	min_val = min(vals)
	min_val_idx = vals.index(min_val)
	vals.remove(min_val)
	vals.insert(0, min_val)
	if min_val_idx == 0:
		min_val_idx = 1
	return (vals[:min_val_idx], vals[min_val_idx:])
q = int(input())
for __ in range(q):
	n = int(input())
	remain_vals = list(map(int, input().split()))
	vals = []
	while remain_vals:
		(new_vals, remain_vals) = min_sort(remain_vals)
		vals += new_vals
	print(' '.join(map(str, vals)))


for case in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	tmp = 0
	nxt = 1
	use = [False for i in range(n + 1)]
	bub = []
	for i in range(n):
		use[p[i]] = True
		if p[i] == nxt:
			p.pop(i)
			p.insert(tmp, nxt)
			nxt += 1
			while nxt <= n and use[nxt]:
				nxt += 1
			if nxt > n:
				break
			tmp = i + 1
			if nxt < p[i]:
				tmp -= 1
	print(' '.join(map(str, p)))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	while l:
		nxt = l.index(min(l))
		print(l[nxt], end=' ')
		if nxt == 0:
			del l[0]
		else:
			print(*l[:nxt - 1], sep=' ')
			if nxt > 1:
				print(' ', end='')
			l[nxt] = l[nxt - 1]
			del l[:nxt]
	print()


q = int(input())
result = []
for i in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	out = []
	x = 0
	while x < n - 1:
		magic = min(arr[x:])
		if arr[x] == magic:
			out.append(magic)
			x += 1
			continue
		magicIndex = arr.index(magic)
		out.append(magic)
		out += arr[x:magicIndex - 1]
		(arr[magicIndex], arr[magicIndex - 1]) = (arr[magicIndex - 1], arr[magicIndex])
		x = magicIndex
	out.append(arr[-1])
	result.append(out)
for i in result:
	print(' '.join(map(str, i)))


from sys import stdin
q = int(stdin.readline().rstrip())
for _ in range(q):
	n = int(stdin.readline().rstrip())
	data = [int(x) for x in stdin.readline().rstrip().split()]
	wrong_v = []
	cn = n - 1
	for (i, j) in zip(list(range(0, n)), data):
		if i + 1 != j:
			wrong_v.append((j, i))
	tmp = set()
	for (d, l) in sorted(wrong_v):
		if l in tmp:
			continue
		while True:
			if l == 0:
				break
			if cn == 0:
				break
			if l in tmp:
				break
			if data[l] < data[l - 1]:
				s = data[l]
				data[l] = data[l - 1]
				data[l - 1] = s
				cn -= 1
			tmp.add(l)
			l -= 1
	for pp in data:
		print(pp, end=' ')
	print('')


import sys
sin = sys.stdin
q = int(sin.readline())
for _ in range(q):
	n = int(sin.readline())
	arr = [int(x) for x in sin.readline().split()]
	high = 0
	done = False
	while high < len(arr):
		m = float('inf')
		idx = -1
		for i in range(high, len(arr)):
			m = min(m, arr[i])
			if m == arr[i]:
				idx = i
		if m == arr[high]:
			high += 1
		else:
			arr.remove(m)
			arr.insert(high, m)
			high = idx
	arr = [str(i) for i in arr]
	print(' '.join(arr))


q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	p = n - 1
	j = 0
	while j < n - 1:
		if p > 0:
			m = j
			for k in range(j + 1, j + p + 1):
				if k < n and l[k] < l[m]:
					m = k
			if j != m:
				l.insert(j, l.pop(m))
				p -= m - j
				j = m
			else:
				j = j + 1
		else:
			break
	print(*l, sep=' ')


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	stack = []
	marked = {}
	i = 0
	j = 1
	result = []
	while j <= n:
		if j not in marked:
			stack = []
			result.append(j)
			while l1[i] != j:
				marked[l1[i]] = 1
				stack.append(l1[i])
				i += 1
			marked[j] = 1
			if stack:
				l1[i] = stack[-1]
				del marked[stack[-1]]
				result.extend(stack[:len(stack) - 1])
			else:
				i += 1
		j += 1
	print(*result, sep=' ')


for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	i = 0
	while i < n:
		m = min(a[i:])
		ind = a.index(m)
		if ind == i:
			i += 1
			continue
		for j in range(ind, i, -1):
			(a[j], a[j - 1]) = (a[j - 1], a[j])
		i = ind
	print(*a)


import sys, math

def input():
	return sys.stdin.readline()[:-1]

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		a = list(map(int, input().split()))
		t = 1
		p = 0
		f = [0 for k in range(n)]
		while t <= n:
			for k in range(p, n):
				if a[k] == t:
					p = k
					for l in range(k, 0, -1):
						if f[l] == 0 and a[l] < a[l - 1]:
							(a[l], a[l - 1]) = (a[l - 1], a[l])
							f[l] = 1
						else:
							break
			t += 1
		print(*a)
main()


from sys import stdin
n = int(input())

def solve(perm, n):
	res = minimizePermutation(perm, n, 1, {})
	return ' '.join((str(x) for x in res))

def minimizePermutation(perm, n, smallest, seen):
	if smallest > n:
		return []
	index = perm.index(smallest)
	(solved, rest) = splitIntoChunks(perm, index)
	for x in solved:
		seen[x] = True
	nextSmallest = smallest + 1
	while nextSmallest in seen:
		nextSmallest += 1
	return solved + minimizePermutation(rest, n, nextSmallest, seen)

def splitIntoChunks(list, index):
	solved = [list[index]] + (list[:index - 1] if index > 0 else [])
	lastBeforeSmallest = [list[index - 1]] if index > 0 else []
	rest = lastBeforeSmallest + list[index + 1:]
	return [solved, rest]
while n > 0:
	x = int(input())
	permutation = list(map(int, stdin.readline().rstrip().split()))
	print(solve(permutation, x))
	n -= 1


q = int(input())
for _ in range(q):
	n = int(input())
	quer = list(map(int, input().split()))
	ops = [1 for i in range(n - 1)]
	flg = True
	while flg:
		flg = False
		for i in reversed(range(0, n - 1)):
			if quer[i] > quer[i + 1] and ops[i] == 1:
				(quer[i], quer[i + 1]) = (quer[i + 1], quer[i])
				ops[i] = 0
				flg = True
	print(*quer, sep=' ')


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	done = []
	while len(p) > 0:
		if len(p) == 1:
			done.extend(p)
			p = []
			break
		mind = p.index(min(p))
		if mind == 0:
			done.append(p[0])
			p = p[1:]
			continue
		change = p[:mind + 1]
		swap = change[-1:] + change[:-1]
		done.extend(swap[:-1])
		p = swap[-1:] + p[mind + 1:]
	print(*done)


I = input
for _ in [0] * int(I()):
	I()
	a = [*map(int, I().split())]
	i = k = 0
	while k < len(a):
		try:
			k += 1
			j = a.index(k, i)
			a[i:j + 1] = [a[j]] + a[i:j]
			i = j + (i == j)
		except:
			pass
	print(*a)


for _ in range(int(input())):
	am = int(input())
	arr = list(map(int, input().split()))
	was = [False] * (am - 1)
	for i in range(am - 1):
		m = 9999999999
		ind = 0
		for g in range(am - 1):
			if not was[g]:
				if arr[g + 1] < m:
					if arr[g + 1] < arr[g]:
						m = arr[g + 1]
						ind = g
		if m == 9999999999:
			break
		was[ind] = True
		(arr[ind], arr[ind + 1]) = (arr[ind + 1], arr[ind])
	print(*arr)


n = int(input())
for i in range(n):
	leng = int(input())
	s_data = input()
	flag = [0] * leng
	data = s_data.split(' ')
	k = 0
	while k < leng:
		j = leng - 1
		while j > 0:
			if flag[j] == 0 and int(data[j]) < int(data[j - 1]):
				flag[j] = 1
				(data[j], data[j - 1]) = (data[j - 1], data[j])
				break
			j -= 1
		k += 1
	print(' '.join(data))


q = int(input())
res = []
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	for m in range(1, n + 1):
		i = a.index(m)
		if i <= l:
			continue
		for j in range(i - 1, l - 1, -1):
			if a[j] < a[j + 1]:
				break
			(a[j], a[j + 1]) = (a[j + 1], a[j])
		l = i
	res.append(' '.join(map(str, a)))
print(*res, sep='\n')


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 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()
		a = li()
		b = [0] * n
		for i in range(1, n + 1):
			ind = -1
			for j in range(n):
				if a[j] == i:
					ind = j
					break
			while ind > 0:
				oz = ind - 1
				if b[oz] == 1:
					break
				if a[oz] < a[ind]:
					break
				b[oz] = 1
				(a[oz], a[ind]) = (a[ind], a[oz])
				ind -= 1
		print(*a)

def __starting_point():
	solve()
__starting_point()


def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')
for _ in range(int(input())):
	n = int(input())
	l = li()
	l1 = sorted(l)
	if l == l1:
		print(*l)
	else:
		visited = {}
		j = 0
		while j < len(l):
			ind = n - 1
			for k in range(j, n):
				if l[ind] > l[k]:
					ind = k
			if ind != j:
				for k in range(ind, j, -1):
					if k not in visited:
						visited[k] = 1
						(l[k], l[k - 1]) = (l[k - 1], l[k])
			j += 1
		print(*l)


import heapq
from sys import stdin, stdout
from collections import defaultdict

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = [int(k) for k in input().split()]
		dic = {}
		freq = [0] * n
		for i in range(n):
			if freq[i] == 0:
				ind = -1
				mn = arr[i]
				for j in range(i + 1, n):
					if arr[j] < mn:
						ind = j
						mn = arr[j]
				if ind != -1:
					for j in range(ind - 1, i - 1, -1):
						temp = arr[j]
						arr[j] = arr[j + 1]
						arr[j + 1] = temp
						freq[j] = 1
		print(*arr)
main()


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	move = 0
	while move < n:
		mini = min(l[move:])
		m_idx = l.index(mini)
		if m_idx == move:
			move += 1
		else:
			l = l[:move] + [mini] + l[move:m_idx] + l[m_idx + 1:]
			move = m_idx
	print(*l)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	mark = [0] * n
	for i in range(1, n + 1):
		ind = a.index(i)
		for j in range(ind, i - 1, -1):
			if mark[j - 1] == 1:
				break
			elif int(a[j - 1]) > int(a[j]):
				temp = a[j]
				a[j] = a[j - 1]
				a[j - 1] = temp
				mark[j - 1] = 1
	for i in range(n):
		print(a[i], end=' ')
	print()


for T in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = n - 1
	f = a.index(1)
	a = [1] + a[:f] + a[f + 1:]
	s -= f
	if f == 0:
		f = 1
	while s > 0:
		b = f
		if a[b:b + s + 1] == list():
			break
		c = min(a[b:b + s + 1])
		f = a.index(c)
		a = a[:b] + [c] + a[b:f] + a[f + 1:]
		s -= f - b
		if f == b:
			f = b + 1
	for i in a:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	pos = 0
	for i in range(1, n):
		if pos == n - 1:
			break
		ind = q.index(i)
		if ind == pos:
			pos += 1
		elif ind > pos:
			q.insert(pos, q.pop(ind))
			pos = ind
	print(*q)


q = int(input())
for j in range(q):
	n = int(input())
	list = [int(i) for i in input().split()]
	k = 0
	for i in range(1, n + 1):
		s = list.index(i)
		if s > k:
			if i < list[k]:
				list.remove(i)
				list.insert(k, i)
				k = s
			else:
				list.remove(i)
				list.insert(k + 1, i)
				k = s
	for i in range(n - 1):
		print(list[i], end=' ')
	print(list[n - 1])


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = [int(x) for x in stdin.readline().split()]
	flags = [0] * n
	any = True
	while any == True:
		any = False
		for i in range(n - 1, 0, -1):
			if arr[i - 1] > arr[i] and flags[i - 1] == 0:
				any = True
				flags[i - 1] = 1
				(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
	for i in arr:
		print(i, end=' ')
	print()


def fun(arr, n):
	rem = n - 1
	i = 0
	while i != n - 1:
		m = min(arr[i + 1:min(i + rem + 2, n)])
		ind = arr.index(m)
		if ind - i <= rem and arr[i] > m:
			rem -= ind - i
			for j in range(ind, i, -1):
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
			i = ind
		else:
			i += 1
		if rem == 0:
			break
for _ in range(int(input())):
	n = int(input())
	arr = [int(n) for n in input().split()]
	fun(arr, n)
	print(*arr)


from queue import Queue
import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	N = int(input())
	A = list(map(int, input().split()))
	Query.append((N, A))
for (N, A) in Query:
	m = 1
	checked = [False] * (N + 1)
	q1 = Queue()
	ans = []
	for a in A:
		if a == m:
			ans.append(m)
			checked[m] = True
			while q1.qsize() > 1:
				b = q1.get()
				ans.append(b)
				checked[b] = True
			while m + 1 < N:
				m += 1
				if not checked[m]:
					break
			if q1.empty():
				continue
			b = q1.get()
			if b == m:
				ans.append(m)
				checked[m] = True
				while m + 1 < N:
					m += 1
					if not checked[m]:
						break
			else:
				q1.put(b)
		else:
			q1.put(a)
	while q1.qsize() > 0:
		a = q1.get()
		ans.append(a)
	for a in ans:
		print(a, end=' ')
	print()


import sys

def swap(nums, i):
	t = nums[i]
	nums[i] = nums[i + 1]
	nums[i + 1] = t

def foo(nums, start, stop):
	if stop - start < 2:
		return
	i = nums.index(min(nums[start:stop]))
	if i != start:
		swap(nums, i - 1)
		foo(nums, start, i)
		foo(nums, i, stop)
	else:
		foo(nums, i + 1, stop)
q = int(next(sys.stdin))
for _ in range(q):
	n = int(next(sys.stdin))
	nums = list(map(int, next(sys.stdin).split(' ')))
	foo(nums, 0, n)
	print(' '.join(map(str, nums)))


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	best = sorted(arr)
	done = {}
	i = 0
	left = 0
	right = n
	best_count = 0
	mi = 1
	ind = arr.index(1)
	while i < n - 1:
		if arr == best:
			break
		if ind > left:
			right = ind
			while ind != left:
				(arr[ind], arr[ind - 1]) = (arr[ind - 1], arr[ind])
				ind -= 1
				i += 1
			left = right
			right = n
		else:
			left += 1
		if left > n - 1:
			break
		mi = min(arr[left:])
		ind = arr.index(mi)
	print(' '.join([str(x) for x in arr]))


from sys import stdin

def solution(t: int) -> None:
	input = stdin.readline
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		d1 = {x: 1 for x in range(1, n)}
		j = n - 1
		while d1 and j > 0:
			tmp = min(d1, key=lambda x: arr[x])
			if arr[tmp] < arr[tmp - 1]:
				(arr[tmp], arr[tmp - 1]) = (arr[tmp - 1], arr[tmp])
			del d1[tmp]
			j -= 1
		print(' '.join(map(str, arr)))

def main():
	t = int(input())
	solution(t)
main()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = [0] * (n - 1)
	for i in range(n - 2, -1, -1):
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			brr[i] = 1
	for i in range(n - 1):
		if arr[i] > arr[i + 1] and brr[i] == 0:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			brr[i] = 1
	print(*arr)


T = int(input())

def m(A):
	if len(A) <= 1:
		return A
	else:
		mi = min(A)
		a = A.index(mi)
		if a == 0:
			return [mi] + m(A[a + 1:])
		return [mi] + A[:a - 1] + m([A[a - 1]] + A[a + 1:])
for i in range(T):
	n = int(input())
	A = [int(i) for i in input().strip().split()]
	A = m(A)
	print(' '.join([str(a) for a in A]))


import sys
q = int(input())
result = []

def swap(arr, x, y):
	(arr[x], arr[y]) = (arr[y], arr[x])
for _ in range(q):
	input()
	a = list(map(int, next(sys.stdin).split(' ')))
	j = 0
	while j < len(a):
		min_el = a[j]
		min_i = j
		for i in range(j, len(a)):
			if a[i] < min_el:
				min_el = a[i]
				min_i = i
		if min_i == j:
			j += 1
		else:
			del a[min_i]
			a.insert(j, min_el)
			j = min_i
	result.append(' '.join(map(str, a)))
print('\n'.join(result))


def min_val(A, n):
	min_val = 1
	vis = [0] * n
	while min_val < n:
		i = A.index(min_val)
		l = i - 1
		while l >= 0 and (not vis[l + 1]) and (A[l] > A[l + 1]):
			(A[l], A[l + 1]) = (A[l + 1], A[l])
			vis[l + 1] = 1
			l -= 1
		min_val += 1
	for a in A:
		print(a, end=' ')
	print()
q = int(input())
while q:
	n = int(input())
	A = [int(s) for s in input().split(' ')]
	min_val(A, n)
	q -= 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [-1] + arr
	pos = [False] * (n + 1)
	mapp = {}
	for i in range(n + 1):
		mapp[arr[i]] = i
	i = 1
	x = 1
	while i < n and x <= n:
		y = mapp[x]
		if y != x and pos[y - 1] is False and (arr[y - 1] > x):
			mapp[x] = y - 1
			mapp[arr[y - 1]] = y
			temp = arr[y - 1]
			arr[y - 1] = x
			arr[y] = temp
			pos[y - 1] = True
			i += 1
		else:
			x += 1
	print(*arr[1:])


q = int(input())
for _ in range(q):
	awa = input()
	n = list(map(int, input().split()))
	c = 1
	last = 0
	i = 0
	while c < len(n):
		if n[i] == c:
			j = i
			while j > last and n[j - 1] > n[j]:
				(n[j], n[j - 1]) = (n[j - 1], n[j])
				j -= 1
			last = i
			c += 1
		i += 1
		if i == len(n):
			i = last
			c += 1
	i = 0
	while i < len(n):
		if i < len(n) - 1:
			print(n[i], end=' ')
		else:
			print(n[i])
		i += 1


query = []
w = 1

def seting(a):
	global query, w
	query[a - 1] = False
	if w == a:
		for i in range(a, len(query)):
			if query[i]:
				w = i + 1
				break
q = int(input())
for _ in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	w = 1
	query = [True] * n
	oper = [True] * (n - 1)
	for i in range(n - 1):
		if w != l[i] and oper[i]:
			for j in range(i + 1, n):
				if l[j] == w:
					b = j
					break
			for j in range(b - 1, i - 1, -1):
				h = l[j + 1]
				l[j + 1] = l[j]
				l[j] = h
				oper[j] = False
			seting(w)
		else:
			seting(l[i])
	print(*l)


def solve(arr):
	n = len(arr)
	moves = n - 1
	index = 0
	while moves > 0:
		min_val = float('inf')
		req_index = -1
		for i in range(index, min(n, index + moves + 1)):
			if arr[i] < min_val:
				min_val = arr[i]
				req_index = i
		moves -= req_index - index
		arr.insert(index, arr.pop(req_index))
		if index == req_index:
			index += 1
		else:
			index = req_index
		if index == n:
			break
	for i in arr:
		print(i, end=' ')
	print()

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr)
main()


import sys

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

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	a = list(mints())
	b = [True] * n
	for i in range(n - 1):
		j = i + 1
		z = (a[i], i)
		while j < n and b[j - 1]:
			z = min(z, (a[j], j))
			j += 1
		if z[0] < a[i]:
			j = z[1] - 1
			while j >= i:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
				b[j] = False
				j -= 1
	print(*a)
for i in range(mint()):
	solve()


for tt in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	pos = 0
	for i in range(1, n):
		if pos == n - 1:
			break
		index = l.index(i)
		if index == pos:
			pos += 1
		elif index > pos:
			l.insert(pos, l.pop(index))
			pos = index
	print(*l)


import sys, math, statistics as ss, collections as cc
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = len(a)
	qw = []
	for j in range(len(a)):
		q = a.index(j + 1)
		while c > 1 and q > j:
			if a[q] < a[q - 1] and q not in qw:
				qw.append(q)
				(a[q], a[q - 1]) = (a[q - 1], a[q])
				c = c - 1
				q = q - 1
			else:
				break
		if c <= 1 or a == sorted(a):
			break
	print(*a)


def solve(p):
	if len(p) <= 1:
		return p
	i = p.index(min(p))
	if i > 0:
		return [p[i]] + p[:i - 1] + solve([p[i - 1]] + p[i + 1:])
	else:
		return [p[0]] + solve(p[1:])
q = int(input())
for case in range(q):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	print(*solve(a))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	cnt = 0
	k = 0
	used = [False] * n
	while cnt < n - 1 and k < n:
		min_v = min(p[k:])
		index = p.index(min_v)
		for i in range(index, 0, -1):
			if not used[i] and cnt < n - 1 and (p[i] < p[i - 1]):
				cnt += 1
				(p[i], p[i - 1]) = (p[i - 1], p[i])
				used[i] = True
		k += 1
	print(' '.join(map(str, p)))


for q in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = 0
	for j in range(1, n):
		if pos == n - 1:
			break
		i = a.index(j)
		if i == pos:
			pos += 1
		elif i > pos:
			a.insert(pos, a.pop(i))
			pos = i
	print(*a)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().strip().split()))
	x = 0
	xx = 1
	j = x
	while j < n:
		j = x
		while j < n and a[j] != xx:
			j += 1
		if j == n:
			xx += 1
			j = x
			continue
		if j == x:
			x += 1
			xx += 1
			continue
		y = a.pop(j)
		a.insert(x, y)
		x = j
		xx += 1
	print(' '.join(list(map(str, a))))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	vis = [0] * n
	for _ in range(1, n):
		(mx, idx) = (101, -1)
		for i in range(0, n - 1):
			if vis[i] == 0 and a[i] > a[i + 1]:
				if mx > a[i + 1]:
					mx = a[i + 1]
					idx = i
		if idx != -1:
			vis[idx] = 1
			(a[idx], a[idx + 1]) = (a[idx + 1], a[idx])
	for i in range(n):
		print(a[i], end=' ')
t = int(input())
while t > 0:
	t -= 1
	solve()
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	visited = set()
	for i in range(len(arr)):
		if i in visited:
			continue
		best_idx = i
		for j in range(i + 1, len(arr)):
			if j in visited:
				break
			if arr[j] < arr[best_idx]:
				best_idx = j
		while best_idx != i:
			visited.add(best_idx - 1)
			(arr[best_idx], arr[best_idx - 1]) = (arr[best_idx - 1], arr[best_idx])
			best_idx -= 1
	print(*arr)


q = int(input())
for _ in range(q):
	n = int(input())
	l = [int(x) for x in input().split()]
	s = [x for x in range(1, n + 1)]
	ans = []
	while len(l):
		ans.append(s.pop(0))
		x = ans[-1]
		temp = []
		while l[0] != x:
			temp.append(l.pop(0))
		l.pop(0)
		if len(temp):
			l.insert(0, temp[-1])
			temp.pop(-1)
			ans.extend(temp)
			for x in temp:
				s.remove(x)
	print(' '.join([str(x) for x in ans]))


n = int(input())
for i in range(n):
	l = int(input())
	p = list(map(int, input().split()))
	k = l - 1
	d = set()
	for j in range(1, l + 1):
		ind = p.index(j)
		if k == 0:
			break
		while ind + 1 != j:
			if k == 0:
				break
			if ind in d or p[ind - 1] < p[ind]:
				break
			else:
				(p[ind], p[ind - 1]) = (p[ind - 1], p[ind])
				d.add(ind)
				k -= 1
			ind = p.index(j)
	print(*p, sep=' ')


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = []
	while a:
		(v, i) = min(((v, i) for (i, v) in enumerate(a)))
		b += [v]
		if i:
			b += a[:i - 1]
			a = a[i - 1:i] + a[i + 1:]
		else:
			a = a[1:]
	print(*b)


q = int(input())
while q:
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	for i in range(1, n + 1):
		if a[i - 1] != i:
			ind = a.index(i)
			if ind < i - 1:
				k = 0
				while ind + k + 1 < n and a[ind + k + 1] < a[ind + k] and (a[i - 1] != i):
					if ind + k in s:
						break
					(a[ind + k], a[ind + k + 1]) = (a[ind + k + 1], a[ind + k])
					s.add(ind + k)
					k += 1
			else:
				k = 1
				while ind - k >= 0 and a[ind - k] > a[ind - k + 1] and (a[i - 1] != i):
					if ind - k in s:
						break
					(a[ind - k], a[ind - k + 1]) = (a[ind - k + 1], a[ind - k])
					s.add(ind - k)
					k += 1
	print(*a)
	q -= 1


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = 0
	while r != n - 1:
		l = r
		r = a.index(min(a[l:]))
		if r == l:
			r = l + 1
			continue
		for i in range(r, l, -1):
			(a[i], a[i - 1]) = (a[i - 1], a[i])
	print(*a)


q = int(input())
for t in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = 0
	while i < n - 1:
		m = min(a[i:])
		i = a.index(m)
		a = a[:j] + [m] + a[j:i] + a[i + 1:]
		if i == j:
			i += 1
		j = i
	print(*a)


import sys
n = int(input())
while n:
	m = int(input())
	nums = list(map(int, input().split()))
	ans = []
	pos = {}
	begin = 0
	len_ = len(nums)
	while begin < len_ - 1:
		min_ = len_ + 1
		for i in range(begin, len_):
			if nums[i] < min_:
				min_ = nums[i]
				min_pos = i
		ans.append(min_)
		if begin != min_pos:
			ans += nums[begin:min_pos - 1]
			(nums[min_pos], nums[min_pos - 1]) = (nums[min_pos - 1], nums[min_pos])
		if begin == min_pos:
			begin += 1
		else:
			begin = min_pos
	ans.append(nums[len_ - 1])
	print(' '.join(list(map(str, ans))))
	n -= 1


q = int(input())
for _ in range(q):
	n = int(input())
	a = [0] + [int(x) for x in input().split()]
	used = [False] * (n + 1)
	k = 0
	while k != n - 1:
		z = k
		for i in range(n - 1, 0, -1):
			if a[i] > a[i + 1] and (not used[i]):
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				used[i] = True
				k += 1
				break
		if z == k:
			break
	print(*a[1:])


for _ in range(int(input())):
	n = int(input())
	seq = [int(x) - 1 for x in input().split()]
	p = 0
	while p < n:
		el = min(seq[p:])
		nxt = seq.index(el)
		seq.remove(el)
		seq.insert(p, el)
		if p == nxt:
			p = nxt + 1
		else:
			p = nxt
	print(' '.join((str(val + 1) for val in seq)))


q = int(input())
while q > 0:
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	while k < n - 1:
		kold = k
		mink = a[k]
		for i in range(n - kold):
			if a[i + kold] < mink:
				k = i + kold
				mink = a[i + kold]
		for i in range(k - kold):
			(a[k - i - 1], a[k - i]) = (a[k - i], a[k - i - 1])
		if k == kold:
			k = k + 1
	for elem in a:
		print(elem, end=' ')
	print()
	q = q - 1


q = int(input())
for _ in [0] * q:
	n = int(input())
	arr = list(map(int, input().split()))
	st = 0
	while st < n:
		j = arr.index(min(arr[st:n]), st)
		arr[st:j + 1] = [arr[j]] + arr[st:j]
		if j == st:
			st += 1
		else:
			st = j
	print(*arr)


def inp(dtype=str, strip=True):
	s = input()
	res = [dtype(p) for p in s.split()]
	res = res[0] if len(res) == 1 and strip else res
	return res

def problem1():
	q = inp(int)
	for _ in range(q):
		(a, b, n, S) = inp(int)
		S = S - min(S // n * n, a * n)
		if S <= b:
			print('YES')
		else:
			print('NO')

def problem2():
	q = inp(int)
	for _ in range(q):
		n = inp(int)
		a = inp(int, strip=False)
		start = 0
		while start < n - 1:
			(mn, pos) = (a[start], start)
			for i in range(start + 1, n):
				if a[i] < mn:
					mn = a[i]
					pos = i
			i = pos - 1
			while i >= start:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				i -= 1
			start = max(pos, start + 1)
		print(' '.join([str(el) for el in a]))

def problem3():
	pass

def problem4():
	pass
problem2()


q = int(input())
for j in range(q):
	n = int(input())
	perm = list(reversed(list(map(int, input().split()))))
	i = n - 1
	ins = n - 1
	for k in range(1, n + 1):
		if i >= perm.index(k):
			i = perm.index(k)
			del perm[i]
			perm.insert(ins, k)
			if i == perm.index(k):
				ins = i - 1
			else:
				ins = i
		if i == 0:
			break
	print(' '.join(map(str, list(reversed(perm)))))


def fmin(st, lis):
	mi = st
	for i in range(st, len(lis)):
		if lis[i] < lis[mi]:
			mi = i
	return mi
q = int(input())
for qq in range(q):
	n = int(input())
	m = list(map(int, input().split()))
	i = 0
	while i < n - 1:
		xi = fmin(i, m)
		m = m[:i] + [m[xi]] + m[i:xi] + m[xi + 1:]
		i = xi + (1 if i == xi else 0)
	print(*m)


import math

def mp(p):
	n = len(p)
	possible_moves = [1 for i in range(n)]
	lowest_seen = 1
	minimal = 1
	for i in range(n):
		if p[i] != i + 1:
			for j in range(i, 0, -1):
				if p[j] == j + 1:
					break
				if p[j - 1] < p[j]:
					break
				if possible_moves[j - 1] == 1:
					t = p[j]
					p[j] = p[j - 1]
					p[j - 1] = t
					possible_moves[j - 1] = 0
			minimal = minimal + 1
	return p

def new_mp(p):
	n = len(p)
	possible_moves = [1 for i in range(n)]
	for i in range(n):
		for j in range(n):
			if p[j] == i:
				for k in range(j, 0, -1):
					if p[k - 1] < p[k]:
						break
					if possible_moves[k - 1] == 1:
						t = p[k]
						p[k] = p[k - 1]
						p[k - 1] = t
						possible_moves[k - 1] = 0
	return p
q = input()
q = int(q)
res = [None for i in range(q)]
for i in range(q):
	n = input()
	p = input()
	p = [int(i) for i in p.split(' ')]
	res[i] = new_mp(p)
for i in range(q):
	s = str(res[i]).replace(', ', ' ').replace('[', '').replace(']', '')
	print(s)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	l = 0
	while l < n - 1:
		r = ar.index(min(ar[l:]))
		for i in range(r, l, -1):
			xx = ar[i]
			ar[i] = ar[i - 1]
			ar[i - 1] = xx
		l = max(r, l + 1)
	print(*ar)


cases = int(input())

def min_elem_idx(arr, ignore):
	min_elem = len(arr) + 100
	min_idx = -1
	for (idx, elem) in enumerate(arr):
		if elem not in ignore and elem < min_elem:
			min_elem = elem
			min_idx = idx
	return (min_elem, min_idx)

def minperm(l, arr):
	used_ops = set()
	visited_nodes = set()
	visited_nodes.add(arr[0])
	while len(visited_nodes) < l and len(used_ops) < l - 1:
		(min_elem, active_idx) = min_elem_idx(arr, visited_nodes)
		visited_nodes.add(min_elem)
		while arr[active_idx] < arr[active_idx - 1] and active_idx not in used_ops and (active_idx > 0):
			used_ops.add(active_idx)
			temp = arr[active_idx]
			arr[active_idx] = arr[active_idx - 1]
			arr[active_idx - 1] = temp
			active_idx -= 1
	print(' '.join(map(str, arr)))
for _ in range(cases):
	l = int(input())
	arr = list(map(int, input().split()))
	minperm(l, arr)


import copy
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = copy.deepcopy(a)
	b.sort()
	done = set()
	itr = 0
	for i in range(n):
		minval = b[i]
		j = a.index(minval)
		while j > 0 and itr < n:
			if j - 1 in done:
				break
			elif minval < a[j - 1]:
				(a[j], a[j - 1]) = (a[j - 1], a[j])
				done.add(j - 1)
				itr += 1
			j -= 1
	print(*a, end=' ')
	print()


q = int(input())
for i in range(q):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	cur = 1
	curpos = 0
	for i in range(n):
		if a[i] == cur:
			for j in range(i, curpos, -1):
				(a[j], a[j - 1]) = (a[j - 1], a[j])
			if i + 1 >= n:
				break
			cur = min(a[i + 1:])
			if cur > a[i]:
				curpos = i + 1
			else:
				curpos = i
	print(' '.join([str(x) for x in a]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = [0] * n
	v = n - 1
	i = 1
	d = {}
	for h in range(n):
		d[l[h]] = h
	for __t in range(n):
		if v:
			w = d[i]
			i += 1
			for t in range(w, -1, -1):
				if t - 1 >= 0 and l[t] < l[t - 1]:
					if k[t - 1] == 0:
						temp = l[t]
						l[t] = l[t - 1]
						l[t - 1] = temp
						k[t - 1] = 1
						v -= 1
				else:
					break
		else:
			break
	print(*l)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	i = 0
	lim = 0
	a = sorted(lis)
	while i < n:
		d = lis.index(a[i])
		if d == lim:
			lim += 1
		elif d > lim:
			g = lis.pop(d)
			lis = lis[:max(0, lim)] + [g] + lis[lim:]
			lim = max(lim, d)
		i += 1
	print(*lis)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	c = n - 1
	for i in range(n):
		x = min(l[i:n])
		if i == x - 1 and l[i] == x:
			k += 1
			continue
		if l[i] == x:
			j = i
			while j > k and c != 0 and (l[j] < l[j - 1]):
				(l[j], l[j - 1]) = (l[j - 1], l[j])
				j -= 1
				c -= 1
			k = i
	print(*l)


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
t = int(input())
for u in range(t):
	b = set()
	n = int(input())
	a = list(map(int, input().split()))
	kol = 0
	for i in range(n):
		if a[i] != i + 1:
			k_i = 0
			for j in range(n):
				if a[j] == i + 1:
					k_i = j
					break
			for j in range(k_i - 1, -1, -1):
				if (j, j + 1) not in b:
					if a[j] > a[j + 1]:
						(a[j], a[j + 1]) = (a[j + 1], a[j])
						b.add((j, j + 1))
						if j == i:
							break
					else:
						break
				else:
					break
	print(*a)


def main():
	b = int(input())
	c = list(map(int, input().split()))
	k = 0
	while k != len(c):
		g = [c[i] for i in range(k, len(c))]
		a = min(g)
		t = c.index(a)
		if c[k] > a:
			b -= t
			for i in range(t, k, -1):
				(c[i], c[i - 1]) = (c[i - 1], c[i])
			k = t
		else:
			k += 1
			b -= 1
	print(*c)
a = int(input())
for i in range(a):
	main()


for q in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pos = 0
	for i in range(1, n):
		if pos == n - 1:
			break
		idx = arr.index(i)
		if idx == pos:
			pos += 1
		elif idx > pos:
			arr.insert(pos, arr.pop(idx))
			pos = idx
	print(*arr)


q = int(input())
for _ in range(q):
	n = int(input())
	perm = list(map(int, input().split()))
	idx = 0
	while idx < n:
		m = perm.index(min(perm[idx:]))
		if m == idx:
			idx += 1
			continue
		for i in range(m, idx, -1):
			(perm[i], perm[i - 1]) = (perm[i - 1], perm[i])
			idx = m
	print(*perm)


q = int(input())
for i in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [arr[0]]
	k = 0
	while k + 1 < n and ans[k] == k + 1:
		ans.append(arr[k + 1])
		k += 1
	if k + 1 != n:
		arr = arr[k + 1:]
		el = 0
		while el <= n:
			if el in arr:
				eli = arr.index(el)
				if ans[-1] > el:
					ans = ans[:-1] + [el] + [ans[-1]] + arr[:eli]
				else:
					ans += [el] + arr[:eli]
				arr = arr[eli + 1:]
			el += 1
		ans += arr
	print(*ans)


def swap(array, i):
	temp = array[i]
	array[i] = array[i + 1]
	array[i + 1] = temp
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	if n == 1:
		print(array[0])
	else:
		flag = [0] * (n - 1)
		for _ in range(n - 2, -1, -1):
			for j in range(n - 2, -1, -1):
				if array[j] > array[j + 1] and flag[j] == 0:
					swap(array, j)
					flag[j] = 1
		print(' '.join(list(map(str, array))))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = a
	q = []
	res = []
	while True:
		p = min(ans)
		q.append([p, a.index(p)])
		ans = a[a.index(p) + 1:n]
		if p == a[-1]:
			break
	start = 0
	fin = []
	for j in q:
		fin += [j[0]] + [a[x] for x in range(start, j[1])]
		start = j[1] + 1
	for j in q:
		if j[1] < n - 1 and fin[j[1]] > fin[j[1] + 1]:
			(fin[j[1]], fin[j[1] + 1]) = (fin[j[1] + 1], fin[j[1]])
	print(*fin)


q = int(input())
for _ in range(q):
	n = int(input())
	s = list(map(int, input().split()))
	pos = 0
	while pos < n:
		k = s.index(min(s[pos:]))
		if k == pos:
			pos += 1
		else:
			t = s[:pos]
			t.append(s[k])
			t.extend(s[pos:k])
			t.extend(s[k + 1:])
			s = t
			pos = k
	print(*s)


q = int(input())
for _ in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	p = 0
	while p < n:
		min_val = min(a[p:])
		i = p
		while a[i] != min_val:
			i += 1
		if i > p:
			for j in range(i, p, -1):
				t = a[j]
				a[j] = a[j - 1]
				a[j - 1] = t
			p = i
		else:
			p = i + 1
	for i in range(n - 1):
		print(a[i], end=' ')
	print(a[n - 1])


q = int(input())
for y in range(q):
	n = int(input())
	list1 = [int(i) for i in input().split()]
	list2 = []
	for x in range(1, n + 1):
		pos = list1.index(x)
		new_pos = pos
		while not new_pos - 1 in list2 and new_pos != 0 and (list1[new_pos - 1] > list1[new_pos]):
			(list1[new_pos - 1], list1[new_pos]) = (list1[new_pos], list1[new_pos - 1])
			new_pos -= 1
			list2.append(new_pos)
	for z in range(n - 1):
		print(list1[z], end=' ')
	print(list1[n - 1])


q = int(input())
i = 1
while i <= q:
	n = int(input())
	per = list(map(int, input().split()))
	oper = [0 for j in range(n)]
	num = 0
	smallest = 1
	while num < n - 1 and smallest <= n:
		for (ind, j) in enumerate(per):
			if j == smallest and ind + 1 == smallest:
				smallest += 1
				break
			elif j == smallest and ind + 1 != smallest:
				if oper[ind] == 0:
					oper[ind] = 1
					temp = per[ind]
					per[ind] = per[ind - 1]
					per[ind - 1] = temp
					num += 1
				elif oper[ind] == 1:
					smallest += 1
					if ind + 1 < n:
						oper[ind + 1] = 1
	for j in per:
		print(j, end=' ')
	print()
	i += 1


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	b = [False] * n
	k = 0
	while k < n - 1:
		c = a[k:].index(min(a[k:])) + k
		flag = False
		for j in range(c - 1, k - 1, -1):
			flag = True
			(a[j], a[j + 1]) = (a[j + 1], a[j])
		k = c
		if not flag:
			k += 1
	print(*a)


a = [0] * 110
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	id = 0
	while id < n - 1:
		pos = id
		res = a[pos]
		idd = id
		while id < n:
			if a[id] < res:
				res = a[id]
				idd = id
			id += 1
		if pos == idd:
			id = idd + 1
			continue
		id = idd
		while idd > pos:
			a[idd] = a[idd - 1]
			idd -= 1
		a[pos] = res
	for it in a:
		print(it, end=' ')
	print('')


q = int(input())
for i in range(q):
	n = int(input())
	a = input().split(' ')
	a = list(map(int, a))
	fl = 0
	while fl < n - 1:
		mel = min(a[fl:])
		minpos = a.index(mel)
		if minpos != fl:
			temp = a[fl:minpos]
			a[fl] = mel
			a[fl + 1:minpos + 1] = temp
			fl = minpos
		else:
			fl += 1
	a = list(map(str, a))
	print(' '.join(a))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	k = n - 1
	i = 0
	while i < n:
		mini = l[i]
		ind = -1
		j = i + 1
		while j < min(n, i + k + 1):
			if l[j] < mini:
				mini = l[j]
				ind = j
			j += 1
		if ind == -1:
			i += 1
			continue
		temp = ind
		while ind > i and k != 0:
			(l[ind], l[ind - 1]) = (l[ind - 1], l[ind])
			ind -= 1
			k -= 1
		i = temp
	print(*l)


import sys
import math

def main():
	for _ in range(int(input())):
		n = int(sys.stdin.readline())
		l = [int(x) for x in sys.stdin.readline().split()]
		flag = [0] * n
		for i in range(n):
			x = l.index(min(l[i:]))
			while x != i and x > 0:
				if flag[x - 1] == 0:
					(l[x], l[x - 1]) = (l[x - 1], l[x])
					flag[x - 1] = 1
					x = x - 1
				else:
					break
		for i in l:
			print(i, end=' ')
		print()
main()


import math

def main():
	tests_count = int(input())
	for _ in range(0, tests_count):
		count = int(input())
		permutations_given = list(map(int, input().split()))
		result_list = []
		while permutations_given:
			smallest = min(permutations_given)
			position = permutations_given.index(smallest)
			permutations_given.remove(smallest)
			result_list.append(smallest)
			if position > 0:
				result_list.extend(permutations_given[:position - 1])
				permutations_given = permutations_given[position - 1:]
		result = ' '.join((str(number) for number in result_list))
		print(result)
main()


q = int(input())

def is_possible(n, a):
	cnt = 0
	while cnt != n - 1:
		i = a.index(min(*a[cnt:n]))
		if cnt == i:
			cnt += 1
		else:
			a.insert(cnt, a.pop(i))
			cnt = i
	print(*a)
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	is_possible(n, a)


q = int(input())
for i in range(q):
	l = int(input())
	p = list(map(int, input().split(' ')))
	used = []
	cur_min = 1
	for i in range(l - 1):
		j = 0
		while j < l:
			if p[j] == cur_min:
				if j == cur_min - 1:
					cur_min += 1
					break
				else:
					while j not in used and j - 1 >= 0 and (p[j] < p[j - 1]):
						(p[j], p[j - 1]) = (p[j - 1], p[j])
						used.append(j)
						j -= 1
					cur_min += 1
			j += 1
	for i in range(0, l):
		print(p[i], end=' ')
	print()


def find_min(ls, l):
	ans = ls[l]
	ind = l
	for i in range(l, len(ls)):
		if ans > ls[i]:
			ind = i
			ans = ls[i]
	return ind

def solve(ls):
	left = 0
	while left < len(ls) - 1:
		ind = find_min(ls, left)
		el = ls.pop(ind)
		ls.insert(left, el)
		if ind == left:
			left = ind + 1
		else:
			left = ind
	return ls
q = int(input())
for i in range(q):
	_ = int(input())
	ls = list(map(int, input().split()))
	ans = solve(ls)
	print(' '.join(map(str, ans)))


t = int(input())
for test in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	ava = [0] * (n - 1)
	op = 1
	curr = 1
	while curr <= n:
		x = p.index(curr)
		if x == 0:
			curr += 1
			continue
		while True:
			if ava[x - 1] == 0:
				if p[x] < p[x - 1]:
					(p[x], p[x - 1]) = (p[x - 1], p[x])
					ava[x - 1] = 1
					op += 1
					x = x - 1
					if x <= 0:
						curr += 1
						break
				else:
					curr += 1
					break
			else:
				curr += 1
				break
	print(*p)


q = int(input())
for i in range(q):
	n = int(input())
	lst = list(map(int, input().split()))
	sign = 0
	if n == 1:
		print(1)
	else:
		for j in range(1, n + 1):
			positionj = lst.index(j)
			if positionj > sign:
				lst.insert(sign, j)
				del lst[positionj + 1]
				sign = positionj
			elif positionj == sign:
				sign += 1
				continue
			else:
				continue
		print(*lst)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ind = 0
	s = 0
	put = 0
	while ind != n - 1:
		ind = arr.index(min(arr[s:]))
		if ind == put:
			s += 1
			put += 1
			continue
		p = arr.pop(ind)
		arr = arr[:put] + [p] + arr[put:]
		s = ind
		put = ind
	print(*arr)


def dequy(a):
	if len(a) == 1:
		return a
	x = min(a)
	k = a.index(x)
	if k == 0:
		return [a[0]] + dequy(a[1:])
	return [x] + a[:k - 1] + dequy([a[k - 1]] + a[k + 1:])
for tc in range(int(input())):
	n = int(input())
	a = dequy(list(map(int, input().split())))
	for i in a:
		print(i, end=' ')
	print()


import re
for _ in range(int(input())):
	n = int(input())
	seq = input().split()
	perm = n - 1
	actVal = n
	actPos = 0
	seq2 = []
	maxIdc = 0
	i = 0
	while i < n - 1:
		maxIdc = i
		for j in range(i + 1, n):
			if int(seq[j]) < int(seq[maxIdc]):
				maxIdc = j
		perm = perm - (maxIdc - i)
		seq2 = seq[0:i] + [seq[maxIdc]] + seq[i:maxIdc] + seq[maxIdc + 1:]
		seq = seq2
		if maxIdc == i:
			i += 1
			continue
		i += maxIdc - i
	print(' '.join([str(x) for x in seq]))


def solve(lst):
	ans = [i for i in lst]
	dcts = {}
	for i in range(len(lst)):
		dcts[lst[i]] = i
	l = 0
	while l < len(lst) - 1:
		p = min(ans[l:])
		if p == ans[l]:
			l += 1
		else:
			ans.pop(dcts[p])
			ans.insert(l, p)
			l = dcts[p]
	return ' '.join([str(i) for i in ans])
m = int(input())
for i in range(m):
	k = int(input())
	lst = list(map(int, input().split(' ')))
	print(solve(lst))


def use(a, start, num):
	global u
	global d
	global me
	k = start
	while k > start - num and k > di:
		if a[k] < a[k - 1]:
			d[a[k] - 1] -= 1
			d[a[k - 1] - 1] += 1
			(a[k], a[k - 1]) = (a[k - 1], a[k])
			u -= 1
		k -= 1
	me = start - num
	return
t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[a[i] - 1] = i
	u = n - 1
	me = 0
	di = -1
	for i in range(n):
		if di >= d[i]:
			continue
		if d[i] - me > u:
			do = d[i]
			use(a, d[i], u)
			di = do
			continue
		do = d[i]
		use(a, d[i], d[i] - i)
		di = do
	print(*a)


from math import inf
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split())) + [inf]
	m = n - 1
	S = set(range(m))
	for __ in range(m):
		ind = n
		for i in S:
			if arr[i] > arr[i + 1] and arr[i + 1] < arr[ind]:
				ind = i + 1
		if ind == n:
			break
		(arr[ind], arr[ind - 1]) = (arr[ind - 1], arr[ind])
		S.remove(ind - 1)
	print(*arr[:-1])


import sys
q = int(sys.stdin.readline())
for _ in range(q):
	n = int(sys.stdin.readline())
	q = [0] + list(map(int, sys.stdin.readline().split()))
	table = [0] * (n + 1)
	for i in range(1, n + 1):
		for k in range(1, n + 1):
			if q[k] == i:
				st = k
				for j in range(k, -1, -1):
					if q[st] < q[j] and table[j] == 0:
						table[j] = 1
						temp = q[st]
						q[st] = q[j]
						q[j] = temp
						st = j
	result = ' '.join(map(str, q[1:]))
	print(result)


for q in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	f = (n + 2) * [0]
	(place, point) = (0, 1)
	for i in range(n):
		f[num[i]] = 1
		if point == num[i]:
			x = i
			while x > place and num[x] < num[x - 1]:
				(num[x], num[x - 1]) = (num[x - 1], num[x])
				x -= 1
			place = i
			while f[point] == 1:
				point += 1
	print(*num)


import sys
import itertools
import math
import collections
from collections import Counter

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
t = ii()
for _ in range(t):
	n = ii()
	d = li()
	res = []
	pos = 0
	c = 1
	i = 0
	while i < n:
		if d[i] == c:
			if i == pos:
				i += 1
				if i == n:
					break
				c = min(d[i:])
				pos += 1
				continue
			for j in range(i, pos, -1):
				(d[j], d[j - 1]) = (d[j - 1], d[j])
			c = min(d[i:])
			pos = i
		else:
			i += 1
	prr(d)


def solve_one(values, prev_idx):
	try:
		value = min(values[prev_idx:])
	except ValueError:
		return prev_idx + 1
	idx = values.index(value, prev_idx)
	if idx > prev_idx:
		values.pop(idx)
		values.insert(prev_idx, value)
		next_idx = idx
	else:
		next_idx = max(idx, prev_idx) + 1
	return next_idx

def solve(values):
	next_idx = 0
	while next_idx < len(values):
		next_idx = solve_one(values, next_idx)
	return values
num_perms = int(input().strip())
for _ in range(num_perms):
	perm_length = int(input().strip())
	perm = list(map(int, input().strip().split(' ')))[:perm_length]
	print(' '.join(map(str, solve(perm))))


def mini(y, a, i, j):
	f = y
	while f > i:
		(a[f], a[f - 1]) = (a[f - 1], a[f])
		f -= 1
	return z
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	z = sorted(a)
	d = {}
	c = 0
	for i in a:
		d[i] = c
		c += 1
	i = 0
	p = 1
	while i < n and p < n:
		y = min(a[i:n])
		if y == a[i]:
			i += 1
			continue
		w = mini(d[y], a, i, n - 1)
		i = d[y]
		p += 1
		if i == n - 1:
			break
	for i in a:
		print(i, end=' ')
	print()


t = int(input())
answer = []

def mini(arr):
	minimum = arr[0]
	index = 0
	for i in range(1, len(arr)):
		if minimum > arr[i]:
			minimum = arr[i]
			index = i
	return index
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	ans = []
	while len(p) > 1:
		index = mini(p)
		ans.append(p[index])
		for k in range(index - 1):
			ans.append(p[k])
		p = p[index - 1:index] + p[index + 1:]
	if len(p) == 1:
		ans.append(p[0])
	answer.append(ans)
for i in range(t):
	print(*answer[i], sep=' ')


def minimum(arr):
	m = 101
	ind = -1
	for i in range(len(arr)):
		if i != 0 and arr[i][0] < m and (arr[i - 1][1] != 1) and (arr[i][0] < arr[i - 1][0]):
			m = arr[i][0]
			ind = i
	return ind - 1
q = int(input())
for i in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		arr[i] = [arr[i], 0]
	for i in range(n - 1):
		ind = minimum(arr)
		if ind >= 0:
			t = arr[ind][0]
			arr[ind] = [arr[ind + 1][0], 1]
			arr[ind + 1][0] = t
	for i in range(n):
		print(arr[i][0], end=' ')
	print()


def solve(n, perm):
	pos = 0
	while pos < n:
		nxt = min(perm[pos:])
		el = perm.index(nxt)
		perm.pop(el)
		perm.insert(pos, nxt)
		if pos == el:
			pos = el + 1
		else:
			pos = el
	print(' '.join(map(str, perm)))
t = int(input())
for _ in range(t):
	n = int(input())
	perm = list(map(int, input().split()))
	solve(n, perm)


q = int(input())
for i in range(q):
	n = int(input())
	mas = list(map(int, input().split()))
	l = 0
	while l + 1 < n:
		now = l
		for i in range(l, n):
			if mas[i] < mas[now]:
				now = i
		if now == l:
			l += 1
		else:
			mas = mas[:l] + [mas[now]] + mas[l:now] + mas[now + 1:]
			l = now
	print(*mas)


import sys

def I():
	return sys.stdin.readline().rstrip()
q = int(I())
for _ in range(q):
	n = int(I())
	l = list(map(int, I().split()))
	i = 0
	while i < len(l) - 1:
		m = min(l[i:])
		mi = l.index(m)
		if i < mi:
			l = l[:i] + [m] + l[i:mi] + l[mi + 1:]
			i = mi
		else:
			i += 1
	print(*l)


R = lambda : map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	L = list(R())
	k = n - 1
	i = 1
	v = [0] * (n - 1)
	while k and i < n:
		ind = L.index(i)
		for j in reversed(range(ind)):
			if k > 0:
				if v[j] == 0 and L[j] > i:
					v[j] = 1
					(L[j], L[j + 1]) = (L[j + 1], L[j])
					k -= 1
			else:
				break
		i += 1
	print(*L)


def fun(ls, lf, rt):
	if lf >= n - 1 or lf > rt:
		return ls
	x = ls.index(min(ls[lf:rt + 1]))
	a = min(ls[lf:rt + 1])
	if x == lf:
		return fun(ls, x + 1, n - 1)
	ls = ls[:lf] + [ls[x]] + ls[lf:x] + ls[x + 1:]
	return fun(ls, x, n - 1)
for t in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	ans = map(lambda x: str(x), fun(l, 0, n - 1))
	print(' '.join(ans))


def check(ar):
	for i in range(1, len(ar)):
		if ar[i] == 0:
			return 1
	return 0
t = int(input())
while t:
	t -= 1
	n = int(input())
	ar = list(map(int, input().split()))
	visited = [0] * (n + 1)
	visit = []
	for i in range(n):
		visit.append(i + 1)
	prev = []
	q = 0
	while prev != ar:
		q += 1
		prev = ar.copy()
		z = 0
		while z < n:
			e = visit[z]
			for i in range(n):
				if ar[i] == e and i != 0 and (visited[i] == 0) and (ar[i - 1] > ar[i]):
					temp = ar[i - 1]
					ar[i - 1] = ar[i]
					ar[i] = temp
					visited[i] = 1
					z = -1
			z += 1
	for i in ar:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = [1] * n
	i = n - 2
	while i >= 0:
		j = i
		while j < n - 1 and arr[j] > arr[j + 1] and (count[j] == 1):
			temp = arr[j]
			arr[j] = arr[j + 1]
			arr[j + 1] = temp
			count[j] = 0
			j += 1
		i -= 1
	for i in arr:
		print(i, end=' ')


for i in range(int(input())):
	v = set()
	a = input()
	a = list(map(int, input().split()))
	k = 0
	m = 1
	while k < len(a):
		if m not in a:
			break
		j = a.index(m)
		if j + 1 == m:
			m = m + 1
		elif j not in v and a[j] < a[j - 1]:
			t = a[j]
			a[j] = a[j - 1]
			a[j - 1] = t
			v.add(j)
			k += 1
		else:
			m = m + 1
	print(' '.join(list(map(str, a))))


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	poss = set()
	for i in range(0, n - 1):
		poss.add(i)
	count = 0
	while len(poss) > 0 and count < n and (p != sorted(p)):
		m = sorted(p)[count]
		for i in range(len(p)):
			if p[i] == m:
				ind = i
				break
		if ind - 1 in poss and p[ind - 1] > p[ind]:
			poss.remove(ind - 1)
			p = p[:ind - 1] + [p[ind]] + [p[ind - 1]] + p[ind + 1:]
		else:
			count += 1
	for i in range(len(p)):
		p[i] = str(p[i])
	print(' '.join(p))


from operator import itemgetter

def MinimizeThePermutation(n, seq):
	i = n - 2
	done = [0] * n
	while i >= 0:
		if seq[i] > seq[i + 1]:
			done[i] += 1
			t = seq[i]
			seq[i] = seq[i + 1]
			seq[i + 1] = t
		i -= 1
	i = 0
	while i < n - 1:
		if done[i] == 0 and seq[i] > seq[i + 1]:
			done[i] += 1
			t = seq[i]
			seq[i] = seq[i + 1]
			seq[i + 1] = t
		i += 1
	result = ' '.join(seq)
	return result

def MinimizeThePermutationOptimization(n, seq):
	i = 0
	while i < n - 1:
		result = ''
		j = i
		minElement = i
		minPos = i
		while j < n - 1:
			if seq[j] < seq[j + 1]:
				minPos = j
				break
			if seq[minElement] > seq[j]:
				minElement = j
			if seq[minElement] > seq[j + 1]:
				minElement = j + 1
			j += 1
		if minPos != i:
			j = minPos
			while j > i:
				t = seq[j]
				seq[j] = seq[j - 1]
				seq[j - 1] = t
				j -= 1
			i = minPos
		elif minElement != i:
			j = minElement
			while j > i:
				t = seq[j]
				seq[j] = seq[j - 1]
				seq[j - 1] = t
				j -= 1
			i = minElement
		else:
			i += 1
	result = ' '.join(seq)
	return result

def minElementMethod(n, seq):
	i = 0
	while i < n:
		minPos = i + min(enumerate(seq[i:]), key=itemgetter(1))[0]
		j = minPos
		while j > i:
			t = seq[j]
			seq[j] = seq[j - 1]
			seq[j - 1] = t
			j -= 1
		if minPos == i:
			i += 1
		else:
			i = minPos
	result = ' '.join((str(x) for x in seq))
	return result
q = int(input())
result = ''
while q > 0:
	n = int(input())
	seq = [int(x) for x in input().split()]
	result += minElementMethod(n, seq)
	if q > 1:
		result += '\n'
	q -= 1
print(result)


def minimize_lexicographically(array):
	if not array:
		return []
	min_item = min(array)
	min_idx = array.index(min_item)
	if min_idx == 0:
		return [min_item] + minimize_lexicographically(array[1:])
	used_part = [min_item] + array[:min_idx - 1]
	unused_part = array[min_idx - 1:min_idx] + array[min_idx + 1:]
	return used_part + minimize_lexicographically(unused_part)
number_of_tests = int(input())
for _ in range(number_of_tests):
	input()
	permutation = [int(x) for x in input().split()]
	result = minimize_lexicographically(permutation)
	print(' '.join([str(x) for x in result]))


q = int(input())
for i in range(0, q, 1):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	isp = 0
	while isp != n - 1:
		m = min(l[isp:n])
		isp = l.index(m)
		l.remove(m)
		l = l[:s] + [m] + l[s:]
		if s == isp:
			isp += 1
		s = isp
	print(*l)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	i = 0
	start = -1
	while i < n:
		x = min(arr[start + 1:])
		ind = arr[start + 1:].index(x)
		ind = ind + start + 1
		for j in range(ind, max(0, start), -1):
			if arr[j] < arr[j - 1]:
				temp = arr[j]
				arr[j] = arr[j - 1]
				arr[j - 1] = temp
		if ind == n - 1:
			break
		start = ind
	print(*arr)


import sys
input = sys.stdin.readline
q = int(input())

def sortper(begin):
	x = A.index(min(A[begin:]))
	return (x, A[:begin] + [A[x]] + A[begin:x] + A[x + 1:])
for testcases in range(q):
	n = int(input())
	A = list(map(int, input().split()))
	begin = 0
	while begin < n - 1:
		(nbegin, A) = sortper(begin)
		if begin == nbegin:
			begin += 1
		else:
			begin = nbegin
	print(*A)


Q = int(input())
for q in range(Q):
	n = int(input())
	a = list(map(int, input().split()))
	idx = {}
	for i in range(n):
		idx[a[i]] = i
	used = [0] * (n - 1)
	k = 1
	while k < n + 1:
		if idx[k] > 0:
			if used[idx[k] - 1] == 0 and a[idx[k]] < a[idx[k] - 1]:
				used[idx[k] - 1] = 1
				(a[idx[k]], a[idx[k] - 1]) = (a[idx[k] - 1], a[idx[k]])
				(idx[a[idx[k]]], idx[a[idx[k] - 1]]) = (idx[a[idx[k] - 1]], idx[a[idx[k]]])
			else:
				k += 1
		else:
			k += 1
	ans = [0] * n
	for i in range(1, n + 1):
		ans[idx[i]] = i
	print(*ans)


for _ in range(int(input())):
	q = int(input())
	n = list(map(int, input().split()))
	pos = 0
	while pos < q:
		nxt = n.index(min(n[pos:]))
		el = n.pop(nxt)
		n.insert(pos, el)
		if pos == nxt:
			pos = nxt + 1
		else:
			pos = nxt
	print(' '.join([str(i) for i in n]))


m = int(input())
for _ in range(m):
	n = int(input())
	arr = list(map(int, input().split()))
	vis = [0] * n
	for i in range(1, n + 1):
		p = 0
		while p < n and arr[p] != i:
			p += 1
		while p > 0 and (not vis[p - 1]) and (arr[p - 1] > arr[p]):
			vis[p - 1] = 1
			(arr[p], arr[p - 1]) = (arr[p - 1], arr[p])
			p -= 1
	print(*arr)


q = int(input())
while q:
	n = int(input())
	v = [int(x) for x in input().split()]
	pos = 0
	while pos < n:
		Min = n + 1
		for i in range(pos, n):
			if v[i] < Min:
				Min = v[i]
				nxt = i
		aux = v[nxt]
		v[pos + 1:nxt + 1] = v[pos:nxt]
		v[pos] = aux
		if pos == nxt:
			pos += 1
		else:
			pos = nxt
	for i in range(n):
		print(str(v[i]), end=' ')
	print()
	q -= 1


t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	b = [0 for i in range(n - 1)]
	c = 0
	temp = []
	while c < n:
		m = 100
		pos = 100
		for i in range(0, n):
			if a[i] < m and a[i] not in temp:
				m = a[i]
				pos = i
		if pos == 100:
			break
		if pos == 0 or b[pos - 1] == 1:
			temp.append(m)
			continue
		if a[pos - 1] > a[pos]:
			z = a[pos]
			a[pos] = a[pos - 1]
			a[pos - 1] = z
			b[pos - 1] = 1
			c += 1
		else:
			temp.append(m)
	for i in a:
		print(i, end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	if n == 1:
		print(*ar)
	elif n == 2:
		ar.sort()
		print(*ar)
	else:
		ans = []
		y = 0
		x = 0
		s = 0
		for j in range(1, n + 1):
			y = s
			while y < n:
				if ar[y] == j:
					for k in range(y, x, -1):
						if ar[k - 1] > ar[k]:
							(ar[k], ar[k - 1]) = (ar[k - 1], ar[k])
					x = y
					s = y
					break
				y += 1
		print(*ar)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	i = n - 2
	count = [0] * (n - 1)
	count1 = 0
	flag = 0
	while count1 < n - 1:
		if count[i] == 0:
			if l[i] > l[i + 1]:
				temp = l[i]
				l[i] = l[i + 1]
				l[i + 1] = temp
				count[i] = 1
				count1 += 1
				i -= 1
				flag = 1
				if i <= -1:
					i = n - 2
					flag = 0
			else:
				i -= 1
				if i <= -1:
					if flag == 0:
						break
					else:
						i = n - 2
						flag = 0
		else:
			i -= 1
			if i <= -1:
				if flag == 0:
					break
				else:
					i = n - 2
					flag = 0
	for i in range(0, len(l) - 1):
		print(l[i], end=' ')
	print(l[len(l) - 1])
	t -= 1


import copy
n = int(input())
for i in range(n):
	m = int(input())
	l = [int(x) for x in input().split()]
	result = []
	if m > 1:
		while m != len(result):
			minimum = min(l)
			j = l.index(minimum)
			li1 = l[:j + 1]
			li2 = l[j + 1:]
			k = copy.deepcopy(li1)
			x = j
			for c in range(x):
				li1[j] = k[j - 1]
				li1[j - 1] = k[j]
				k = copy.deepcopy(li1)
				j -= 1
			if len(result) != 0:
				if li1[0] < result[len(result) - 1]:
					b = li1[0]
					li1[0] = result[len(result) - 1]
					result[len(result) - 1] = b
			for a in li1:
				result.append(a)
			l = li2
		for y in result:
			print(y, end=' ')
		print()
	else:
		print(l[0])


def getMinPos(a, start, m):
	for i in range(start, len(a)):
		if a[i] == m:
			return i
	return -1

def solve(n, a):
	ret = []
	start = 0
	while start < len(a):
		m = getMinPos(a, start, min(a[start:]))
		if m != start:
			a = a[:start] + [a[m]] + a[start:m] + a[m + 1:]
			start = m
		else:
			start += 1
	return ' '.join(map(str, a))
for q in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))


import math
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	l1 = l
	for i in range(n):
		d[l[i]] = i
	j = 1
	i = 1
	op = [0] * n
	cnt = 0
	while j <= n and cnt < n - 1:
		if d[j] > j - 1:
			if op[d[j] - 1] == 0 and l[d[j] - 1] > l[d[j]]:
				op[d[j] - 1] = 1
				temp = l[d[j]]
				l[d[j]] = l[d[j] - 1]
				l[d[j] - 1] = temp
				d[l[d[j]]] = d[j]
				d[j] = d[j] - 1
				cnt += 1
			else:
				j += 1
		else:
			j += 1
	for i in range(n):
		print(l[i], end=' ')
	print()
	t -= 1


def bestFromRevPerm(rp, rpLen, ins=0):
	if ins == 0:
		return bestFromRevPerm(rp[1:], rpLen - 1, ins=rp[0])
	for i in range(rpLen):
		if rp[i] < ins:
			nextbfrp = bestFromRevPerm(rp[i + 1:], rpLen - (i + 1), rp[i])
			if nextbfrp[0] > ins:
				nextbfrp = [nextbfrp[0]] + [ins] + nextbfrp[1:]
			else:
				nextbfrp = [ins] + nextbfrp
			return rp[:i] + nextbfrp
	return rp + [ins]

def printList(l, llen=-1):
	if llen < 0:
		llen = len(l)
	for i in range(llen):
		print(l[i], end=' ' if i < llen - 1 else '')
	print()
for i in range(int(input())):
	n = int(input())
	revPerm = list(map(int, input().split()))[::-1]
	bestPerm = bestFromRevPerm(revPerm, n)[::-1]
	printList(bestPerm, n)


t = int(input())
for j in range(0, t):
	n = int(input())
	str_arr = input().split()
	v = [int(num) for num in str_arr]
	mx = n - 1
	cnt = 0
	while mx > 0 and cnt < n:
		ti = mx + 1
		mid = cnt
		i = 0
		for i in range(mid, min(ti + mid, n)):
			if v[i] < v[mid]:
				mid = i
		cc = v[mid]
		del v[mid]
		v.insert(cnt, cc)
		mx = mx - (mid - cnt)
		if mid == cnt:
			cnt = mid + 1
		else:
			cnt = mid
	for i in range(0, n - 1):
		print(v[i], end=' ')
	print(v[n - 1])


q = int(input())
for i in range(q):
	n = int(input())
	a = [*map(int, input().split())]
	s = 0
	m = 0
	while n - m > 1:
		m = a.index(min(a[s:s + n - m]))
		if m == s:
			s += 1
			continue
		for j in range(m - s):
			(a[m - j], a[m - j - 1]) = (a[m - j - 1], a[m - j])
		s = m
	print(*a)


def outp(arr):
	for i in arr:
		print(i, end=' ')
	print()

def findMin(arr, offset):
	minn = arr[0]
	index = 0
	for i in range(len(arr)):
		if minn > arr[i]:
			minn = arr[i]
			index = i
	return (minn, index + offset)

def so(arr, left, right, flag):
	if left >= right - 1:
		return
	minn = findMin(arr[left:right], left)
	if minn[1] == left:
		left += 1
		so(arr, left, right, 1)
	else:
		for i in range(minn[1], left, -1):
			arr[i] = arr[i - 1]
		arr[left] = minn[0]
		left = minn[1]
		so(arr, left, right, 0)

def core():
	size = int(input())
	arr = [int(i) for i in input().split()]
	left = 0
	right = len(arr)
	so(arr, left, right, 1)
	return arr

def main():
	loop = int(input())
	for i in range(loop):
		outp(core())
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	tmp = 0
	nxt = 1
	used = [False] * (n + 1)
	for i in range(n):
		used[a[i]] = True
		if a[i] == nxt:
			a.pop(i)
			a.insert(tmp, nxt)
			nxt += 1
			while nxt <= n and used[nxt]:
				nxt += 1
			if nxt > n:
				break
			tmp = i + 1
			if nxt < a[i]:
				tmp -= 1
	print(' '.join(map(str, a)))


q = int(input())
res = []
for _ in range(q):
	n = int(input())
	p = list(map(int, input().strip().split(' ')))
	steps = n - 1
	k = 0
	while steps > 0 and k < n - 1:
		min_idx = k
		for (i, v) in enumerate(p[k:]):
			if v < p[min_idx]:
				min_idx = k + i
		if min_idx != k:
			if steps >= min_idx - k:
				steps -= min_idx - k
				val = p.pop(min_idx)
				p.insert(k, val)
				k = min_idx
			else:
				val = p.pop(min_idx)
				p.insert(min_idx - steps, val)
				steps = 0
		else:
			k += 1
	res.append(p)
for item in res:
	print(' '.join([str(v) for v in item]))


q = int(input())
while q:
	q -= 1
	n = int(input())
	(*a,) = map(int, input().split())
	u = [False for i in range(n + 1)]
	u[0] = True
	for i in range(1, n + 1):
		for j in range(n):
			if a[j] == i:
				x = j
				while not u[x] and a[x] < a[x - 1]:
					(a[x], a[x - 1]) = (a[x - 1], a[x])
					u[x] = True
					x -= 1
	print(*a)


t = int(input())

def solve():
	n = int(input())
	p = [int(x) for x in input().split()]
	ps = sorted(p)
	v = [False] * (n - 1)
	m = n - 1
	i = 0
	while m > 0 and i < n:
		low = ps[i]
		index = p.index(low)
		if index == 0:
			i += 1
			continue
		if p[index] < p[index - 1] and (not v[index - 1]):
			(p[index], p[index - 1]) = (p[index - 1], p[index])
			m -= 1
			v[index - 1] = True
		else:
			i += 1
	print(' '.join([str(x) for x in p]))
for _ in range(t):
	solve()


from collections import defaultdict
from math import sqrt, factorial, gcd, log2, inf, ceil
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	i = 1
	cnt = 0
	x = 0
	seti = set()
	while i < n + 1:
		z = l.index(i)
		for j in range(z, 0, -1):
			if l[j - 1] > l[j] and j - 1 not in seti:
				(l[j], l[j - 1]) = (l[j - 1], l[j])
				seti.add(j - 1)
				cnt += 1
				if cnt == n - 1:
					break
			else:
				break
		if cnt == n - 1:
			break
		i += 1
	print(*l)


import sys
input = sys.stdin.readline

def main():
	q = int(input())
	for _ in range(q):
		N = int(input())
		A = [int(x) for x in input().split()]
		ma = 0
		for i in range(1, N + 1):
			ai = A.index(i)
			if ai == ma:
				ma += 1
				continue
			elif ai <= ma:
				continue
			tmp = A[ma:ai]
			A[ma] = i
			A[ma + 1:ai + 1] = tmp
			ma = ai
			if ma == N - 1:
				break
		print(*A)
main()


q = int(input())
for _ in range(q):
	n = int(input())
	arr = [0, *map(int, input().split())]
	c = [0 for _ in range(n + 1)]
	for j in range(n + 1):
		c[arr[j]] = j
	ops = [1 for _ in range(n - 1)]
	ops.insert(0, 0)
	num = 1
	for i in range(n - 1):
		while num == c[num] and num < n:
			num += 1
		if num == n:
			break
		while ops[c[arr[c[num] - 1]]] == 0 and num < n - 1:
			num += 1
		if ops[c[arr[c[num] - 1]]] != 0 and arr[c[num]] < arr[c[num] - 1]:
			ops[c[arr[c[num] - 1]]] = 0
			(arr[c[num] - 1], arr[c[num]]) = (arr[c[num]], arr[c[num] - 1])
			c[num] -= 1
			c[arr[c[num] + 1]] += 1
		else:
			num += 1
			continue
	print(*arr[1:])


t = int(input())
i = 0
somme = sum
while i < t:
	n = int(input())
	x = [int(c) for c in str(input()).split()]
	y = [0] * n
	k = 0
	while k < n:
		j = n - 2
		while j >= 0:
			if y[j] == 0 and x[j] > x[j + 1]:
				y[j] = 1
				(x[j + 1], x[j]) = (x[j], x[j + 1])
			j -= 1
		k += 1
	h = 0
	while h < n - 1:
		print(x[h], end=' ')
		h += 1
	print(x[h])
	i += 1


q = int(input())
for _ in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [(0, 0)] + sorted([(a[i], i) for i in range(n)])
	k = 0
	used = [False] * (n + 1)
	for j in range(1, n + 1):
		for i in range(b[j][1], j - 1, -1):
			if not used[i] and a[i] < a[i - 1]:
				used[i] = True
				(a[i - 1], a[i]) = (a[i], a[i - 1])
				k += 1
				if k == n - 1:
					break
		if k == n - 1:
			break
	print(*a)


q = int(input())
for k in range(q):
	n = int(input())
	rep = n - 1
	s = [int(_) for _ in input().split()]
	i = 0
	l = len(s)
	while i < l:
		m = min(s[i:])
		ind = s.index(m)
		if ind > i:
			s.insert(i, m)
			s.pop(ind + 1)
			i += ind - i
			continue
		i += 1
	for i in s:
		print(i, end=' ')
	print()


t = int(input())
for T in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	val = [0] * n
	v = 1
	while v <= n:
		for i in range(n):
			for j in range(n - 1):
				if l[j] == v:
					if val[j] == 0:
						if l[j] > l[j + 1]:
							(l[j + 1], l[j]) = (l[j], l[j + 1])
							val[j] = 1
				elif l[j + 1] == v:
					if val[j + 1] == 0:
						if l[j] > l[j + 1]:
							(l[j + 1], l[j]) = (l[j], l[j + 1])
							val[j + 1] = 1
			if l[n - 1] == v:
				if val[n - 1] == 0:
					if l[n - 2] > l[n - 1]:
						(l[n - 2], l[n - 1]) = (l[n - 1], l[n - 2])
		else:
			v += 1
	print(*l)


q = int(input())
for queries in range(q):
	n = int(input())
	usados = [0] * n
	lista = list(map(int, input().split()))
	l2 = sorted(lista)
	j = 0
	while min(usados) == 0:
		miniI = lista.index(l2[j])
		i = miniI
		while i > 0 and usados[i] == 0 and (lista[i] < lista[i - 1]):
			(lista[i], lista[i - 1]) = (lista[i - 1], lista[i])
			usados[i] = 1
			i -= 1
		j += 1
		if j >= len(l2):
			break
	print(*lista)


from typing import List

def minimize_the_permutation(n: int, a: List[int]) -> List[int]:

	def swap(i: int):
		index_of[a[i - 1]] += 1
		index_of[a[i]] -= 1
		(a[i - 1], a[i]) = (a[i], a[i - 1])
	index_of = {a[i]: i for i in range(n)}
	swap_until = 0
	focus_on = 1
	while focus_on <= n and swap_until < n - 1:
		i = index_of[focus_on]
		if i > swap_until:
			for j in range(index_of[focus_on] - swap_until):
				swap(i - j)
			swap_until = i
		elif i == swap_until:
			swap_until += 1
		focus_on += 1
	return a

def test():
	assert minimize_the_permutation(5, [5, 4, 1, 3, 2]) == [1, 5, 2, 4, 3]
	assert minimize_the_permutation(4, [1, 2, 4, 3]) == [1, 2, 3, 4]
	assert minimize_the_permutation(1, [1]) == [1]
	assert minimize_the_permutation(4, [4, 3, 2, 1]) == [1, 4, 3, 2]
	assert minimize_the_permutation(5, [1, 2, 5, 4, 3]) == [1, 2, 3, 5, 4]
	assert minimize_the_permutation(5, [2, 5, 1, 4, 3]) == [1, 2, 3, 5, 4]
q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	permutation = minimize_the_permutation(n, a)
	print(' '.join(map(str, permutation)))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction
from heapq import *
from random import randint

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		j = 0
		while j < n:
			mi = inf
			ind = j
			for k in range(j, n):
				if mi > a[k]:
					mi = a[k]
					ind = k
			for k in range(ind, j, -1):
				(a[k], a[k - 1]) = (a[k - 1], a[k])
			j = ind + (ind == n - 1 or ind == j)
		print(*a)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


T = int(input())
for t in range(T):
	n = int(input())
	p = [int(x) for x in input().split()]
	a = [i for (v, i) in sorted(((v, i) for (i, v) in enumerate(p)))]
	ind = [a[0]]
	last = a[0]
	for i in range(1, n):
		if a[i] > last:
			last = a[i]
			ind.append(last)
	s = 0
	for i in range(len(ind)):
		f = ind[i]
		k = p[f]
		if k > p[s]:
			s += 1
		for j in range(f, s, -1):
			p[j] = p[j - 1]
		p[s] = k
		s = f
	print(*p)


q = int(input())
for _ in range(q):
	n = int(input())
	y = list(map(int, input().split()))
	arr = [0] * (n + 1)
	arr[0] = 1
	j = 0
	while j < n:
		ind = y.index(j + 1)
		i = ind - 1
		while i >= 0:
			if arr[i + 1] != 1:
				if y[i] > y[i + 1]:
					t = y[i]
					y[i] = y[i + 1]
					y[i + 1] = t
					arr[i + 1] = 1
				else:
					arr[ind] = 1
			else:
				break
			i -= 1
		j += 1
	print(*y)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	y = n * [0]
	k = 0
	for _ in range(1, n):
		for j in range(1, n):
			if l[-j] < l[-j - 1] and y[j] == 0:
				y[j] = 1
				a = l[-j]
				l[-j] = l[-j - 1]
				l[-j - 1] = a
	ch = ''
	for i in l:
		ch += str(i) + ' '
	print(ch)


amt = int(input())
for _ in range(amt):
	n = int(input())
	nums = list(map(int, input().split()))
	available = nums.copy()
	free = [1 for x in range(len(nums))]
	while len(available) > 0:
		lowest = min(available)
		loc = nums.index(lowest)
		if loc > 0 and free[loc - 1]:
			while loc > 0 and free[loc - 1]:
				if nums[loc - 1] > nums[loc]:
					(nums[loc], nums[loc - 1]) = (nums[loc - 1], nums[loc])
					free[loc - 1] = 0
				else:
					available.remove(lowest)
					break
		else:
			available.remove(lowest)
	print(' '.join([str(x) for x in nums]))


def p_v(v):
	for i in v:
		print(i, end=' ')
	return

def max_p(v, used):
	ind_f = 0
	ind_s = 1
	mx_ind_s = -1
	mx = 0
	for i in range(len(v) - 1):
		if v[ind_f] > v[ind_s] and used[ind_s] == 0:
			if ind_s > mx:
				mx = ind_s
				mx_ind_s = ind_s
		ind_f += 1
		ind_s += 1
	return (mx_ind_s, used)
m = int(input())
for i in range(m):
	n = int(input())
	v = a = list(map(int, input().split()))
	used = [0 for i in range(n)]
	if len(v) == 1:
		p_v(v)
	else:
		for j in range(n - 1):
			(mx_ind, used) = max_p(v, used)
			if mx_ind > -1 and used[mx_ind] == 0:
				used[mx_ind] = 1
				t = v[mx_ind]
				v[mx_ind] = v[mx_ind - 1]
				v[mx_ind - 1] = t
			else:
				break
		p_v(v)


import statistics
import math
import datetime
import collections
import heapq
__author__ = 'Zumrat Kochshegulov'
__contact__ = 'topcoderkz[at]gmail.com'

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		nums = [int(x) for x in input().split()]
		h = nums[:]
		heapq.heapify(h)
		m = heapq.heappop(h)
		was = set()
		for _ in range(n - 1):
			while True:
				index = nums.index(m)
				if index == 0 or nums[index - 1] < nums[index] or index - 1 in was:
					if not h:
						break
					m = heapq.heappop(h)
					continue
				(nums[index], nums[index - 1]) = (nums[index - 1], nums[index])
				was.add(index - 1)
				break
		print(*nums)
main()


import sys
input = sys.stdin.readline
li2 = []
q = int(input())
for _ in range(q):
	li2 = []
	n = int(input())
	li = list(map(int, input().split()))
	k = n - 1
	i = 1
	while li:
		while li and li[0] == min(li):
			li2.append(min(li))
			li.remove(min(li))
		i += 1
		if not li:
			break
		i = min(li)
		while i in li and li.index(i) > k:
			i += 1
		ind = li.index(i)
		k -= ind
		li.remove(i)
		li2.append(i)
		li2.extend(li[:ind - 1])
		li = li[ind - 1:]
	li2 = [str(x) for x in li2]
	print(' '.join(li2))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	u = [0 for x in range(n)]
	for i in range(1, n + 1):
		pos = 0
		while a[pos] != i:
			pos += 1
		while pos > 0 and u[pos - 1] == 0 and (a[pos] < a[pos - 1]):
			u[pos - 1] = 1
			c = a[pos - 1]
			a[pos - 1] = a[pos]
			a[pos] = c
			pos -= 1
	for x in a:
		print(x, '', end='')
	print()
tt = int(input())
while tt > 0:
	solve()
	tt -= 1


t = int(input())
for i in range(0, t):
	l = input()
	p = [int(a) for a in input().split(' ')]
	n = 0
	while n < len(p):
		m = n
		for j in range(m, len(p)):
			if p[j] < p[m]:
				m = j
		if m > n:
			p.insert(n, p.pop(m))
			n = m
		else:
			n = n + 1
	print(' '.join(map(str, p)))


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	while i != n - 1:
		i2 = a.index(min(a[i:]))
		if i2 == i:
			i += 1
		else:
			a.insert(i, a.pop(i2))
			i = i2
	print(*a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	j = 0
	while j < n:
		mi = n + 1
		ind = j
		for k in range(j, n):
			if mi > a[k]:
				mi = a[k]
				ind = k
		for k in range(ind, j, -1):
			(a[k], a[k - 1]) = (a[k - 1], a[k])
		j = ind + (ind == n - 1 or ind == j)
	print(*a)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	gg = 1
	for z in range(1, n + 1):
		for x in range(n):
			if A[x] == z:
				r = x
				ggg = gg
				while r >= gg and A[r] < A[r - 1]:
					(A[r - 1], A[r]) = (A[r], A[r - 1])
					r -= 1
					ggg = x + 1
				gg = ggg
	print(*A)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	usado = -1
	D = [0 for _ in range(n)]
	c = 1
	while c < n:
		i = A.index(c)
		while i > 0 and A[i] < A[i - 1] and (not D[i - 1]):
			D[i - 1] = 1
			temp = A[i]
			A[i] = A[i - 1]
			A[i - 1] = temp
			i -= 1
		c += 1
	for i in range(n):
		print(A[i], end=' ')
	print()


q = int(input())

def swap(arr, i1, i2):
	temp = arr[i1]
	arr[i1] = arr[i2]
	arr[i2] = temp

def solve():
	n = int(input())
	a = [int(x) - 1 for x in input().split()]
	pos = 0
	while pos < n:
		ind = a.index(min(a[pos:]))
		if ind == pos:
			pos += 1
		else:
			val = a.pop(ind)
			a.insert(pos, val)
			pos = ind
	for i in a:
		print(i + 1, end=' ')
	print()
for _ in range(q):
	solve()


for tc in [0] * int(input()):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	j = 0
	while i < n - 1:
		m = min(a[i:])
		i = a.index(m)
		a = a[:j] + [m] + a[j:i] + a[i + 1:]
		if i == j:
			i += 1
		j = i
	print(*a)


t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	f = 1
	q = 0
	k = 1
	while f != 0:
		p = b.index(min(b[q:n]))
		j = p
		while j >= q + 1:
			t = b[j]
			b[j] = b[j - 1]
			b[j - 1] = t
			j += -1
		if p == n - 1:
			f = 0
			break
		if q == p:
			q += 1
		else:
			q = p
	print(*b)


queries = int(input())
for x in range(queries):
	n = int(input())
	perm = input().split()
	perm = [int(x) for x in perm]
	count = 0
	while count < len(perm) - 1:
		least = min(perm[count:])
		index = perm.index(least)
		if index == count:
			count += 1
			continue
		del perm[index]
		perm.insert(count, least)
		count = index
	for x in perm:
		print(x, end=' ')
	print('\n')


import sys
tests = int(sys.stdin.readline())
for _ in range(tests):
	n = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	cnt = 0
	while cnt < n:
		min_element = arr.index(min(arr[cnt:]))
		el = arr[min_element]
		del arr[min_element]
		arr.insert(cnt, el)
		if cnt == min_element:
			cnt = min_element + 1
		else:
			cnt = min_element
	print(' '.join(list(map(str, arr))))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

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

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(l()[0]):
	n = l()[0]
	A = l()
	d = []
	B = sorted(A)
	while len(A) > 1 and len(B):
		(bc, Ac) = (B[:], A[:])
		y = B[0]
		x = A.index(y)
		if x not in d and x > 0 and (A[x] < A[x - 1]):
			(A[x], A[x - 1]) = (A[x - 1], A[x])
			d.append(x)
		else:
			del B[0]
		if len(d) == n - 1 or (B == bc and A == Ac):
			break
	print(*A)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

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

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = I()
	rr = []
	for _ in range(t):
		n = I()
		a = LI()
		j = -1
		for c in range(1, n + 1):
			nj = i = a.index(c)
			while j < i and i >= c and (a[i] < a[i - 1]):
				(a[i], a[i - 1]) = (a[i - 1], a[i])
				i -= 1
			j = max(j, nj)
		rr.append(JA(a, ' '))
	return JA(rr, '\n')
print(main())


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	i = p.index(1)
	p = [1] + p[:i] + p[i + 1:]
	while not i == n - 1:
		x = min(p[i:])
		j = p.index(x)
		if j == i:
			i += 1
			continue
		p = p[:i] + [x] + p[i:j] + p[j + 1:]
		i = j
	print(' '.join(list(map(str, p))))


import random

def get_many_ints():
	return map(int, input().split())

def get_int():
	return int(input())

def prog():
	N = get_int()
	t = list(get_many_ints())
	move = [False] + [True] * N
	for el in range(1, N):
		i = t.index(el)
		while move[i]:
			(t[i], t[i - 1]) = (t[i - 1], t[i])
			move[i] = False
			i -= 1
		move[i + 1] = False
	print(' '.join(map(str, t)))
t = get_int()
for _ in range(t):
	prog()


I = lambda : int(input())
ID = lambda : map(int, input().split())
IL = lambda : list(ID())
q = I()
for _ in range(q):
	n = I()
	a = IL()
	l = 0
	r = n
	while l < n - 1:
		idx = a.index(min(a[l:r]))
		if idx != l:
			k = a.pop(idx)
			a.insert(l, k)
			l = idx
		else:
			l += 1
	for i in range(n):
		print(a[i], end=' ')


def solve(a, n):
	st = 0
	while st < n - 1:
		mni = st
		for i in range(st + 1, n):
			if a[i] < a[mni]:
				mni = i
		print(a[mni], end=' ')
		if mni > st:
			for j in range(st, mni - 1):
				print(a[j], end=' ')
			a[mni] = a[mni - 1]
			st = mni
		else:
			st = mni + 1
	print(a[st])
q = int(input())
for i in range(q):
	n = int(input())
	solve([int(x) for x in input().split()], n)


q = int(input())
for i in range(q):
	n = int(input())
	perm = list(map(int, input().split()))

	def swap(i, j):
		(perm[i], perm[j]) = (perm[j], perm[i])
	curIndex = 0
	while curIndex < n:
		move = min(range(curIndex, n), key=lambda x: perm[x])
		for i in range(move - 1, curIndex - 1, -1):
			swap(i, i + 1)
		if move != curIndex:
			curIndex = move
		else:
			curIndex += 1
	print(' '.join(map(str, perm)))


def move_left(el):
	for i in range(len(op)):
		if op[i][1] == el:
			return i
	return -1
q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	op = [[0 for c in range(n)] for r in range(n)]
	for i in range(1, n):
		op[i][i - 1] = 1
	for i in range(n):
		if p[i] == i + 1 and i > 0:
			op[i][i - 1] = 0
		else:
			break
	for i in range(n):
		minel = p.index(max(p))
		for i in range(1, n):
			if op[i][i - 1] == 1:
				if p[i] < p[minel]:
					minel = i
		while minel > 0 and op[minel][minel - 1] == 1:
			if p[minel] < p[minel - 1]:
				op[minel][minel - 1] = 0
				(p[minel], p[minel - 1]) = (p[minel - 1], p[minel])
				minel -= 1
			else:
				break
		op[minel][minel - 1] = 0
	print(' '.join(map(str, p)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] -= 1
	pos = [0] * n
	used = [False] * (n - 1)
	for i in range(n):
		pos[a[i]] = i
	for i in range(n):
		if not pos[i]:
			continue
		while True:
			if pos[i] > 0 and a[pos[i]] < a[pos[i] - 1] and (not used[pos[i] - 1]):
				pos[a[pos[i] - 1]] += 1
				(a[pos[i]], a[pos[i] - 1]) = (a[pos[i] - 1], a[pos[i]])
				used[pos[i] - 1] = True
				pos[i] -= 1
			else:
				break
	for i in range(n):
		print(a[i] + 1, end=' ')
	print()


from sys import stdin
for _ in range(int(input())):
	l = int(stdin.readline().rstrip())
	a = list(map(int, stdin.readline().rstrip().split(' ')))
	top = 0
	cnt = 0
	while top < l - 1:
		idx = a.index(min(a[top:]))
		if top == idx:
			top += 1
			continue
		a.insert(top, a.pop(idx))
		top = idx
	print(*a)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 1
	i = 0
	l2 = [i for i in range(1, n + 1)]
	w = l.index(c)
	l3 = []
	while i != n - 1:
		if c == l.index(c) + 1 and c < n:
			if l == l2:
				break
			c += 1
			w = l.index(c)
		elif l == l2:
			break
		elif w - 1 in l3:
			c += 1
			if c >= n:
				break
			w = l.index(c)
		elif l[w] < l[w - 1]:
			dck = l[w]
			l[w] = l[w - 1]
			l[w - 1] = dck
			l3.append(w - 1)
			w -= 1
			i += 1
		else:
			c += 1
			if c >= n:
				break
			w = l.index(c)
	for i in l:
		print(i, end=' ')
	print()


import math
t = int(input())
while t:
	n = int(input())
	a = input().split(' ')
	used = []
	for i in range(0, n):
		a[i] = int(a[i])
		used.append(0)
	for i in range(0, n):
		if used[i]:
			continue
		p = i
		for j in range(i + 1, n):
			if a[j] < a[p]:
				p = j
		for j in range(p - 1, i - 1, -1):
			temp = a[j + 1]
			a[j + 1] = a[j]
			a[j] = temp
			used[j] = 1
	for i in range(0, n):
		print(a[i], end=' ')
	print('')
	t -= 1


from sys import stdin
from collections import defaultdict

def find_pos(val):
	for i in range(n):
		if arr[i] == val:
			return i

def swap(first, second):
	(arr[first], arr[second]) = (arr[second], arr[first])
q = int(stdin.readline().strip())
for _ in range(q):
	n = int(stdin.readline().strip())
	arr = list(map(int, stdin.readline().split()))
	done = set()
	for i in range(1, n + 1):
		pos = find_pos(i)
		k = pos - 1
		while k >= 0 and k not in done:
			if arr[k] < arr[k + 1]:
				break
			swap(k, k + 1)
			done.add(k)
			k -= 1
	print(*arr)


import math
q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	num = 1
	pos = 0
	while num < n:
		i = l.index(num)
		if i > pos:
			l.pop(i)
			l.insert(pos, num)
		else:
			i += 1
		pos = max(pos, i)
		num += 1
	for i in l:
		print(i, end=' ')
	print()


q = int(input())
for loop in range(q):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = []
	nq = []
	nex = 1
	end = [False] * (n + 1)
	for i in range(n):
		if lis[i] == nex:
			end[lis[i]] = True
			ans.append(lis[i])
			for j in range(len(nq) - 1):
				end[nq[j]] = True
				ans.append(nq[j])
			while end[nex] and nex < n:
				nex += 1
			if len(nq) > 0:
				nq = [nq[-1]]
				if nq[0] == nex:
					end[nq[0]] = True
					ans.append(nq[0])
					nq = []
					while end[nex] and nex < n:
						nex += 1
		else:
			nq.append(lis[i])
	for i in nq:
		ans.append(i)
	print(' '.join(map(str, ans)))


def Min(arr, l, r, n):
	_min = n
	index = 0
	for i in range(l, r + 1):
		if arr[i] < _min:
			_min = arr[i]
			index = i
	if _min == arr[l]:
		return -1
	return index

def Ans(arr, l, index):
	temp = arr[index]
	for i in range(index, l, -1):
		arr[i] = arr[i - 1]
	arr[l] = temp

def MinAns(arr, l, r, n):
	if l < n:
		index = Min(arr, l, r, n)
		if index == -1:
			return MinAns(arr, l + 1, r, n)
		Ans(arr, l, index)
		if l < r:
			MinAns(arr, index, r, n)
q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split(' ')))
	MinAns(p, 0, n - 1, n)
	for i in p:
		print(i, end=' ')


from sys import stdin, stdout, exit
for i in stdin:
	q = int(i.strip())
	break

def func(L, k):
	if len(L) > 1 and L[0] == min(L):
		return [L[0]] + func(L[1:], k - 1)
	elif len(L) <= 1:
		return L
	else:
		x = L.index(min(L))
		xx = x
		k = k - x
		while x:
			(L[x - 1], L[x]) = (L[x], L[x - 1])
			x -= 1
		return L[:xx] + func(L[xx:], k)
for i in range(q):
	for i in stdin:
		n = int(i)
		break
	for i in stdin:
		L = list(map(int, i.strip().split()))
		break
	L = list(map(str, func(L, len(L))))
	stdout.write(' '.join(L) + '\n')


def print1(l):
	for i in l:
		print(i, end=' ')
	print()
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 1
	l1 = []
	lrem = []
	lans = []
	a1 = 0
	a2 = 0
	while a2 != len(l) - 1:
		a2 = l.index(k)
		for i in range(a2, a1, -1):
			(l[i], l[i - 1]) = (l[i - 1], l[i])
		k = k + 1
		while k in l[:a2]:
			k = k + 1
		if a1 == a2:
			a1 = a2 + 1
		else:
			a1 = a2
	print1(l)


Q = int(input())
for _ in range(Q):
	n = int(input())
	A = list(map(int, input().split()))
	pos = 0
	while pos < n - 1:
		m = min(A[pos:])
		ind = A.index(m)
		if pos == ind:
			pos += 1
			continue
		A = A[:pos] + [m] + A[pos:ind] + A[ind + 1:]
		pos = ind
		if pos == n - 1:
			break
	print(*A)


q = int(input())
for Q in range(q):
	n = int(input())
	x = input()
	a = []
	a = x.split(' ')
	for i in range(n):
		a[i] = int(a[i])
	j = 0
	swaps = 0
	final = []
	while j != n - 1:
		c = []
		for i in range(n):
			c.append(a[i])
		m = min(c[j:])
		for i in range(j, n):
			if c[i] == m:
				pos = i
				break
		for i in range(pos, j, -1):
			a[i] = a[i - 1]
		a[j] = m
		if pos == j:
			j = j + 1
		else:
			j = pos
	for i in range(n - 1):
		print(a[i], end=' ')
	print(a[n - 1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prev = 0
	for i in range(1, n + 1):
		ind = a.index(i)
		if ind > prev:
			for k in range(ind, prev, -1):
				if a[k - 1] < a[k]:
					break
				c = a[k]
				a[k] = a[k - 1]
				a[k - 1] = c
			prev = ind
	print(*a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mark = [0] * n
	count = 0
	inplace = 0
	while True:
		flag = True
		for i in range(n - 2, -1, -1):
			if a[i] > a[i + 1] and mark[i] == 0:
				flag = False
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				mark[i] = 1
				count += 1
			if count == n - 1:
				break
		if count == n - 1 or flag:
			break
	for num in a:
		print(num, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	q = [int(x) for x in input().split()]
	s = set()
	for i in range(n - 1):
		k = n - i - 2
		for j in range(k, n - 1, 1):
			if not j in s and q[j] > q[j + 1]:
				(q[j], q[j + 1]) = (q[j + 1], q[j])
				s.add(j)
	print(' '.join([str(x) for x in q]))


import sys
readline = sys.stdin.readline
rdw = lambda : readline().rstrip()
rdws = lambda : readline().split()
rdwl = lambda : list(readline().split())
rdi = lambda : int(readline())
rdis = lambda : map(int, readline().split())
rdil = lambda : list(map(int, readline().split()))
rdilrows = lambda cnt: [rdil() for _ in range(cnt)]

def solve():
	n = rdi()
	a = rdil()
	sa = sorted([(v, i) for (i, v) in enumerate(a)])
	cur = 0
	for (x, i) in sa:
		if i == cur or (cur < n and x == a[cur]):
			cur += 1
		elif i > cur:
			a[cur + 1:i + 1] = a[cur:i]
			a[cur] = x
			cur = i
	print(' '.join(map(str, a)))
tests = 1
tests = rdi()
for testnum in range(tests):
	solve()


q = int(input())
for j in range(q):
	n = int(input())
	ch = input()
	l = ch.split()
	for i in range(n):
		l[i] = int(l[i])
	if n == 1:
		print(l[0])
	else:
		s = set(range(n))
		s.remove(0)
		s.add(n)
		if l[0] == 1:
			i = 2
		else:
			i = 1
			h = l.index(1)
			for k in range(h):
				s.remove(k + 1)
			while h > 0:
				x = l[h]
				l[h] = l[h - 1]
				l[h - 1] = x
				h -= 1
			i = 2
		while s and i < n:
			h = l.index(i)
			if l[h] < l[h - 1] and h in s:
				x = l[h - 1]
				l[h - 1] = l[h]
				l[h] = x
				s.remove(h)
			else:
				i += 1
		for m in range(n):
			print(l[m], end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	lst = [int(i) for i in input().split()]
	lst2 = []
	for i in range(n - 1, 0, -1):
		lst2.append(i)
		if lst[i] < lst[i - 1]:
			(lst[i - 1], lst[i]) = (lst[i], lst[i - 1])
			lst2.remove(i)
	for kk in range(len(lst2)):
		for i in lst2:
			if lst[i] < lst[i - 1]:
				(lst[i - 1], lst[i]) = (lst[i], lst[i - 1])
	for j in lst:
		print(j, end=' ')
	print()


n = int(input())
for _ in range(n):
	k = int(input())
	l = list(map(int, input().split()))
	d = []
	for x in range(1, k + 1):
		i = l.index(x)
		while i > 0:
			if i == 0 or l[i - 1] < x:
				break
			if x < l[i - 1] and (i - 1, i) not in d:
				l[i] = l[i - 1]
				l[i - 1] = x
				d.append((i - 1, i))
			i -= 1
	print(*l)


q = int(input())
for tc in range(q):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	pl = [0] * (n + 1)
	cnt = 0
	for i in arr:
		pl[i] = cnt
		cnt += 1
	nw = 0
	for i in range(1, n + 1, 1):
		if pl[i] == nw:
			nw += 1
		elif pl[i] > nw:
			tmp = pl[i]
			for j in range(pl[i], nw, -1):
				(pl[arr[j]], pl[arr[j - 1]]) = (pl[arr[j - 1]], pl[arr[j]])
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
			nw = tmp
	print(*arr)


q = int(input())
for _ in range(q):
	n = int(input())
	array = list(map(int, input().split()))
	first = 0
	last = n
	while first < n - 1:
		ind = array.index(min(array[first:last]))
		if ind != first:
			k = array.pop(ind)
			array.insert(first, k)
			first = ind
		else:
			first += 1
	print(*array)


tc = int(input())
for _ in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	done = [False for i in range(n)]
	for z in range(n):
		swapped = False
		for i in range(len(arr) - 2, -1, -1):
			if arr[i] > arr[i + 1] and done[i] == False:
				temp = arr[i]
				arr[i] = arr[i + 1]
				arr[i + 1] = temp
				done[i] = True
				swapped = True
		if swapped == False:
			break
	arr = list(map(str, arr))
	print(' '.join(arr))


n = int(input())
for sas in range(n):
	l = int(input())
	m = list(map(int, input().split()))
	m2 = sorted(m)
	done = 0
	for i in m2:
		ind = m.index(i)
		if ind == done:
			done += 1
		elif ind > done:
			for j in range(ind, done, -1):
				t = m[j]
				m[j] = m[j - 1]
				m[j - 1] = t
			done = ind
	print(*m)


q = int(input())
for _ in range(q):
	n = int(input())
	A = [int(x) for x in input().split()]
	s = set()
	s1 = set()
	temp = 0
	res = []
	while temp != len(A) - 1:
		x = min(A[temp:])
		y = A.index(x)
		if y == temp:
			temp += 1
		else:
			for i in reversed(range(temp + 1, y + 1)):
				A[i] = A[i - 1]
			A[temp] = x
			temp = y
	print(*A)


from sys import stdin
n = int(input())

def solve(perm, n):
	res = minimizePermutation(perm, n, 1, {})
	return ' '.join((str(x) for x in res))

def minimizePermutation(perm, n, smallest, seen):
	if smallest > n:
		return []
	index = perm.index(smallest)
	slice = perm[:index]
	sliceWithoutLast = slice[:-1]
	last = [slice[-1]] if index > 0 else []
	for x in sliceWithoutLast:
		seen[x] = True
	nextSmallest = smallest + 1
	while nextSmallest in seen:
		nextSmallest += 1
	return [smallest] + sliceWithoutLast + minimizePermutation(last + perm[index + 1:], n, nextSmallest, seen)
while n > 0:
	x = int(input())
	permutation = list(map(int, stdin.readline().rstrip().split()))
	print(solve(permutation, x))
	n -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	z = n - 1
	x = 0
	while x < n - 1:
		m = min(l[x:])
		idx = l.index(m)
		l1 = l[0:x] + [m] + l[x:idx]
		if idx + 1 < n:
			l1 += l[idx + 1:]
		l = l1
		if idx == x:
			x = idx + 1
		else:
			x = idx
	for k in l:
		print(k, end=' ')
	print()


import sys
for q in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	d = [int(i) for i in sys.stdin.readline().split()]
	ans = []
	ind = 0
	while len(d):
		mn = min(d)
		mni = d.index(mn)
		if mni == 0:
			ans.append([d[0]])
			d = d[1:]
			continue
		d1 = [mn] + d[:mni - 1]
		d = [d[mni - 1]] + d[mni + 1:]
		ans.append(d1)
	aa = []
	for aaa in ans:
		aa += aaa
	print(*aa)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cc = 0
	dic = {i: 0 for i in range(n)}
	while cc < n:
		ch = 0
		for ind in range(n - 1, 0, -1):
			if a[ind] < a[ind - 1] and dic[ind] == 0:
				(a[ind], a[ind - 1]) = (a[ind - 1], a[ind])
				cc += 1
				dic[ind] = 1
			else:
				ch += 1
		if ch == n - 1:
			break
	print(*a)


def solve(elems):
	i = 0
	j = len(elems)
	while i < len(elems) - 1:
		min_index = i
		for k in range(i, j):
			if elems[min_index] > elems[k]:
				min_index = k
		for m in range(min_index - 1, i - 1, -1):
			(elems[m], elems[m + 1]) = (elems[m + 1], elems[m])
		if min_index == i:
			i += 1
			continue
		i = min_index
	return ' '.join([str(e) for e in elems])
q = int(input())
for _ in range(q):
	n = int(input())
	elems = [int(r) for r in input().split(' ')]
	print(solve(elems))


def opt(arr, n):
	start = 0
	while start != n - 1:
		pos = arr.index(min(arr[start:]))
		if pos == start:
			start += 1
			continue
		temp = arr.pop(pos)
		arr.insert(start, temp)
		start = pos
q = int(input())
for i in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	opt(arr, n)
	for j in range(n):
		print(arr[j], end=' ')
	print()


q = int(input())
for _ in range(q):
	n = int(input())
	num = list(map(int, input().split()))
	cnt = 0
	i = 0
	while i < n - 1:
		target = -1
		minval = 1000
		for j in range(i, n):
			if num[j] < minval:
				target = j
				minval = num[j]
		if target == i:
			i += 1
			continue
		for j in range(target, i, -1):
			(num[j], num[j - 1]) = (num[j - 1], num[j])
		i = target
	for ch in num:
		print(ch, end=' ')
	print()


def fn(n, a):
	v = [False] * n
	for i in range(1, n + 1):
		c = a.index(i) - 1
		while c >= 0:
			if a[c] > a[c + 1] and v[c] == False:
				v[c] = True
				(a[c], a[c + 1]) = (a[c + 1], a[c])
			c = c - 1
	return ' '.join((str(x) for x in a))
m = int(input())
for i in range(m):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(str(fn(n, a)))


import sys, math, queue, collections
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	while i < n:
		mna = min(a[i:])
		j = a.index(mna)
		a = a[:i] + [mna] + a[i:j] + a[j + 1:]
		if i == j:
			i += 1
		else:
			i = j
	print(*a)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = n - 1
	moves = [0] * (n - 1)
	mi = 1
	while mi < n:
		x = arr.index(mi)
		if mi == x + 1:
			mi += 1
		elif moves[x - 1] == 0 and arr[x - 1] > arr[x]:
			temp = arr[x - 1]
			arr[x - 1] = arr[x]
			arr[x] = temp
			moves[x - 1] = 1
		else:
			mi += 1
	print(*arr)


import math

def getMin(a):
	ind = 0
	num = math.inf
	for i in range(len(a)):
		if a[i] < num:
			num = a[i]
			ind = i
	return ind

def test(a, ans):
	if len(a) == 0:
		return ans
	ind = getMin(a)
	if ind == 0:
		ans += [a[ind]]
		return test(a[ind + 1:].copy(), ans)
	else:
		ans += [a[ind]] + a[:ind - 1]
		return test([a[ind - 1]] + a[ind + 1:].copy(), ans)
tests = int(input())
for i in range(tests):
	input()
	a = list(map(int, input().split()))
	print(' '.join(list(map(str, test(a, [])))))


n = int(input())
for nn in range(n):
	_ = input()
	arr = [int(x) for x in input().split(' ')]
	check = [0] * (len(arr) - 1)
	for i in range(len(arr)):
		smallest = i + 1
		index = arr.index(smallest)
		while index != 0 and check[index - 1] == 0 and (arr[index - 1] > arr[index]):
			(arr[index - 1], arr[index]) = (arr[index], arr[index - 1])
			check[index - 1] = 1
			index = index - 1
	print(*arr)


from sys import stdin, stdout
from collections import defaultdict as df
import bisect
q = int(stdin.readline())
for ii in range(q):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	if list(sorted(a)) == a:
		print(*a)
		continue
	elif a[-1] == 1:
		a.pop()
		a.insert(0, 1)
		print(*a)
		continue
	visited = [0] * n
	temp = []
	for i in range(n):
		temp.append((a[i], i))
	j = 0
	ans = []
	temp.sort()
	region = -1
	finalans = []
	while 1:
		mini = min(a)
		index = a.index(mini)
		if index == 0:
			finalans.append([mini])
			a.pop(0)
			if len(a) == 0:
				break
			elif list(sorted(a)) == a:
				finalans.append(a)
				break
			continue
		local = a[index - 1:]
		local.pop(local.index(mini))
		y = a[0:index - 1]
		y = [mini] + y
		finalans.append(y)
		a = [] + local
		if len(a) == 0:
			break
		elif list(sorted(a)) == a:
			finalans.append(a)
			break
	pakka = []
	for i in finalans:
		pakka = pakka + i
	print(*pakka)


import sys
input = sys.stdin.readline
q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	pos = 0
	for i in range(1, n):
		if pos == n - 1:
			break
		idx = a.index(i)
		if idx == pos:
			pos += 1
		elif idx > pos:
			for j in range(idx, pos, -1):
				(a[j], a[j - 1]) = (a[j - 1], a[j])
			pos = idx
	print(*a)


for z in range(int(input())):
	n = int(input())
	ll = list(map(int, input().split()))
	ll = [x - 1 for x in ll]
	pos = 0
	while pos < n:
		nxt = ll.index(min(ll[pos:]))
		el = ll[nxt]
		ll.pop(nxt)
		ll.insert(pos, el)
		if pos == nxt:
			pos += 1
		else:
			pos = nxt
	ll = [x + 1 for x in ll]
	print(*ll)


def calc(l, perm=[]):
	if len(l) <= 1:
		return perm + [str(l[0])]
	else:
		p = min(l)
		q = l.index(p)
		if q == 0:
			return calc(l[1:], perm=perm + [str(p)])
		l.pop(q)
		l.insert(0, p)
		return calc(l[q:], perm=perm + [str(o) for o in l[:q]])
for i in range(int(input())):
	input()
	x = [int(x) for x in input().split()]
	print(' '.join(calc(x)))


q = int(input())
while q > 0:
	n = int(input())
	arr = [int(i) for i in input().split()]
	res = []
	mina = 1
	while len(arr) > 1:
		mina = min(arr)
		pos = arr.index(mina)
		arr.pop(pos)
		res.append(mina)
		if pos:
			pos -= 1
			res += arr[0:pos]
			arr = arr[pos:]
	res += arr
	print(*res, sep=' ')
	q -= 1


def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	(low, high) = (0, n - 1)
	while low < high:
		(minValue, minInd) = (n + 10, -1)
		for ind in range(low, high + 1):
			if arr[ind] < minValue:
				(minValue, minInd) = (arr[ind], ind)
		for ind in reversed(range(low + 1, minInd + 1)):
			(arr[ind], arr[ind - 1]) = (arr[ind - 1], arr[ind])
		low = low + 1 if low == minInd else minInd
	print(' '.join(map(str, arr)))
query = int(input())
for _ in range(query):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	inp = list(map(int, input().split()))
	count = n - 1
	now = 0
	while count > 0 and now < len(inp):
		k = min(inp[now:])
		a = inp.index(k)
		if now == a:
			now = a + 1
			continue
		count -= a - now
		inp.remove(k)
		inp = inp[:now] + [k] + inp[now:]
		now = a
	for item in inp:
		print(item, end=' ')
	print(' ')


import sys

def readline():
	return input()

def fun(n, v):
	used = [False] * n
	for i in range(1, n):
		a = v.index(i) - 1
		while a >= 0:
			if not used[a] and v[a] > v[a + 1]:
				used[a] = True
				(v[a], v[a + 1]) = (v[a + 1], v[a])
			a = a - 1
	return ' '.join((str(x) for x in v))
q = int(readline())
for i in range(q):
	n = int(readline())
	v = list(map(int, readline().split(' ')))
	ans = fun(n, v)
	print(str(ans))


def f(n, lis):
	ops = 0
	light = [False] * (n - 1)
	prev = lis[:]
	prev[0] = 0
	while ops <= n - 1 and prev != lis:
		prev = lis[:]
		for i in range(n - 2, -1, -1):
			if not light[i] and lis[i + 1] < lis[i]:
				(lis[i], lis[i + 1]) = (lis[i + 1], lis[i])
				light[i] = True
				ops += 1
	return lis
for _ in range(int(input())):
	n = int(input())
	print(*f(n, list(map(int, input().split()))))


def swap(arr, start, end):
	for i in range(1, end - start):
		(arr[end - i], arr[end - i - 1]) = (arr[end - i - 1], arr[end - i])
	return arr

def find_min(arr, start, end):
	index = start
	min = arr[start]
	for i in range(start + 1, end):
		if arr[i] < min:
			min = arr[i]
			index = i
	return index
q = int(input())
for i in range(0, q):
	n = int(input())
	arr = [int(x) for x in input().split(' ', n)]
	index = 0
	while index < n:
		min_el_ind = find_min(arr, index, n)
		arr = swap(arr, index, min_el_ind + 1)
		if index == min_el_ind:
			index += 1
		else:
			index = min_el_ind
	print(' '.join([str(x) for x in arr]))


from os import path
import sys
from math import ceil, floor, gcd, log
from collections import defaultdict, Counter
maxx = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
else:
	I = lambda : int(sys.stdin.buffer.readline())
	tup = lambda : map(int, sys.stdin.buffer.readline().split())
	lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
	S = lambda : sys.stdin.readline().replace('\n', '').strip()
	stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
	star = lambda x: print(' '.join(map(str, x)))
for _ in range(I()):
	n = I()
	ls = lint()
	cnt = 0
	ar = []
	for i in range(n - 1):
		if cnt < n - 1:
			for j in range(n - 1, 0, -1):
				if cnt < n - 1:
					if (j, j - 1) not in ar:
						if ls[j] < ls[j - 1]:
							(ls[j], ls[j - 1]) = (ls[j - 1], ls[j])
							cnt += 1
							ar.append((j, j - 1))
		else:
			break
	print(*ls)


import sys
input = sys.stdin.readline
q = int(input())
for _ in range(q):
	w = int(input())
	e = list(map(int, input().split()))
	minpos = []
	mn = w - 1
	m = min(e)
	nn = e.index(m)
	while mn - nn > 0 and w > 0:
		mn -= nn
		if nn > 1:
			minpos += [m] + e[:nn - 1]
			e = [e[nn - 1]] + e[nn + 1:]
		elif nn == 0:
			minpos += [m]
			e = e[nn + 1:]
			w -= 1
		else:
			minpos += [m]
			e = [e[nn - 1]] + e[nn + 1:]
		w -= nn
		if w > 0:
			m = min(e)
			nn = e.index(m)
	if w > 0:
		e = e[:nn - mn] + [e[nn]] + e[nn - mn:nn] + e[nn + 1:]
		minpos += e
	print(*minpos)


import math
import sys
from collections import defaultdict
from itertools import groupby
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

def main():
	t = ri()
	for _ in range(t):
		n = ri()
		a = rl()
		pos = 0
		while pos < n:
			pos_min = pos
			for i in range(pos + 1, n):
				if a[i] < a[pos_min]:
					pos_min = i
			for i in range(pos_min - 1, pos - 1, -1):
				(a[i], a[i + 1]) = (a[i + 1], a[i])
			if pos_min > pos:
				pos = pos_min
			else:
				pos += 1
		print(*a)
main()


for _ in ' ' * int(input()):
	a = int(input())
	b = list(map(int, input().split()))
	p = 0
	for i in range(1, a + 1):
		if b.index(i) > p:
			z = b.index(i)
			b.remove(i)
			b.insert(p, i)
			p = z
		elif b.index(i) == p:
			p += 1
	print(*b)


def correct_it(arr):
	if len(arr) == 1:
		return arr
	m = min(arr)
	j = arr.index(m)
	arr.pop(j)
	arr.insert(0, m)
	if j == 0:
		return arr[:j + 1] + correct_it(arr[j + 1:])
	else:
		return arr[:j] + correct_it(arr[j:])

def permutation(arr, l):
	if l == 1:
		return [1]
	for i in range(l):
		if arr[i] != i + 1:
			return arr[:i] + correct_it(arr[i:])
	return arr
q = int(input())
for index in range(q):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = permutation(arr, n)
	for x in arr:
		print(x, end=' ')
	print()


def get(line):
	if len(line) == 1:
		return line
	a = line.index(min(line))
	if a == 0:
		return [line[0]] + get(line[1:])
	return [line[a]] + line[:a - 1] + get([line[a - 1]] + line[a + 1:])
for _ in range(int(input())):
	n = int(input())
	line = list(map(int, input().split()))
	print(*get(line))


from sys import stdin
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, stdin.readline().split()))
	from_ = 0
	while from_ < n - 1:
		mn = min(a[from_:])
		minI = a.index(mn)
		if from_ < minI:
			a = a[:from_] + [mn] + a[from_:minI] + a[minI + 1:]
			from_ = minI
		else:
			from_ += 1
	print(*a)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	tmp = list(map(int, sys.stdin.readline().split()))
	j = 0
	while True:
		l = j
		mi = n + 1
		for i in range(j, n):
			if mi > tmp[i]:
				mi = tmp[i]
				j = i
		if j == l:
			j += 1
		else:
			for i in range(j, l, -1):
				tmp[i] = tmp[i - 1]
			tmp[l] = mi
		if j >= n - 1:
			break
	for x in tmp:
		print(x, end=' ')
	print()


q = int(input())
for i in range(q):
	n = int(input())
	target = 0
	a = [int(x) for x in input().split()]
	while target + 1 < len(a):
		smallest = 10000
		pos = -1
		for i in range(target, len(a)):
			if a[i] < smallest:
				smallest = a[i]
				pos = i
		if pos != target and pos - target < n:
			n -= pos - target
			rep = a[pos]
			for j in range(pos, target, -1):
				a[j] = a[j - 1]
			a[target] = rep
			target = pos
		else:
			target += 1
	for x in a:
		print(x, end=' ')
	print()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = -1
	i1 = 0
	p = 0
	while i != n - 1:
		i = a.index(min(a[i1:]))
		if i == i1:
			i1 += 1
			continue
		p = a[i]
		del a[i]
		a = a[:i1] + [p] + a[i1:]
		i1 = i
	print(*a)


from math import *
from sys import stdin
input = stdin.readline
IN = lambda : map(int, input().split())
for _ in range(int(input())):
	(_, i) = (int(input()), 0)
	a = [*IN()]
	while a[i:]:
		j = a.index(min(a[i:]))
		a.insert(i, a.pop(j))
		i = j + (j == i)
	print(*a)


q = int(input())
for j in range(q):
	n = int(input())
	a = [int(s) for s in input().split(' ')]
	shift = 0
	while n > 0 and shift < len(a) - 1:
		mina = a[shift]
		min_ind = shift
		for i in range(shift, min(shift + n, len(a))):
			if a[i] < mina:
				mina = a[i]
				min_ind = i
		for i in range(min_ind, shift, -1):
			a[i] = a[i - 1]
		a[shift] = mina
		n -= min_ind - shift
		if min_ind == shift:
			shift += 1
		else:
			shift = min_ind
	print(' '.join([str(el) for el in a]))


import sys
q = int(sys.stdin.readline())
for x in range(q):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	if n == 1:
		print(a[0])
	else:
		marked = [0] * n
		start = 1
		c = 0
		while c < n - 1:
			done = 0
			ind = -2
			for g in range(n):
				if start == a[g]:
					ind = g
				if start == a[g] and g == start - 1:
					done = 1
					break
			if done == 1:
				start += 1
				c += 1
				continue
			else:
				for h in range(ind, 0, -1):
					if marked[h - 1] == 0 and a[h] < a[h - 1]:
						(a[h], a[h - 1]) = (a[h - 1], a[h])
						marked[h - 1] = 1
			start += 1
			c += 1
		for g in range(n):
			print(a[g], end=' ')
		print()


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
cases = int(input())
for q in range(cases):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)[::-1]
	f = 0
	v = b.pop()
	pos = a.index(v)
	c = 0
	d = {(i, j): True for i in range(n) for j in range(n)}
	while c < n - 1 and b:
		while c < n - 1 and pos > 0 and (v < a[pos - 1]):
			if d[pos, pos - 1]:
				d[pos, pos - 1] = False
				(a[pos - 1], a[pos]) = (v, a[pos - 1])
				pos -= 1
				c += 1
			else:
				break
		v = b.pop()
		pos = a.index(v)
	print(*a)


q = int(input())
for i in range(q):
	n = int(input())
	A = list(map(int, input().split()))
	B = []
	k = 1
	for i in range(n):
		j = A.index(k)
		if j != -1 and j not in B:
			if len(B) == 0:
				g = 0
			else:
				g = max(B) + 1
			A.pop(j)
			A.insert(g, k)
			for f in range(g, j):
				B.append(f)
			if j == g:
				B.append(j)
		k += 1
	print(*A)


q = input()
for i in range(int(q)):
	n = input()
	perm = [int(x) for x in input().split()]
	bloq = 0
	while bloq < int(n) - 1:
		mn = min(perm[bloq:])
		pos = perm.index(mn)
		if bloq == pos:
			bloq = bloq + 1
		else:
			perm.pop(pos)
			perm.insert(bloq, mn)
			bloq = pos
	print(' '.join((str(x) for x in perm)))


for _ in range(int(input())):
	n = int(input())
	p = [0] + list(map(int, input().split()))
	cur = 1
	bar = 1
	free = [True] * (n + 1)
	free[0] = False
	for i in range(1, n + 1):
		if p[i] == cur:
			j = i
			while free[j - 1] and p[j - 1] > cur:
				(p[j], p[j - 1]) = (p[j - 1], p[j])
				free[j - 1] = False
				j -= 1
			if i < n:
				cur = min(p[i + 1:])
	print(' '.join(list(map(str, p))[1:]))


q = int(input())
for i in range(q):
	n = int(input())
	nums = [int(s) for s in input().split()]
	start = 0
	while start < n:
		min = n + 1
		end = n + 1
		for i in range(start, n):
			if nums[i] < min:
				min = nums[i]
				end = i
		if start == end:
			start += 1
			continue
		for i in range(end, start, -1):
			nums[i] = nums[i - 1]
		nums[start] = min
		start = end
	prt = ' '.join((str(n) for n in nums))
	print(prt)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0 for _ in range(n)]
	for k in range(n):
		for i in range(len(a)):
			if a[i] == k + 1:
				for j in range(i, k, -1):
					if dp[j - 1] == 0 and a[j - 1] > a[j]:
						(a[j], a[j - 1]) = (a[j - 1], a[j])
						dp[j - 1] = 1
					else:
						break
	for i in range(len(dp) - 1):
		if dp[i] == 0:
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				dp[i] = 1
	for i in range(n):
		print(a[i], end=' ')
	print()
	return
t = int(input())
while t:
	main()
	t -= 1


ct = int(input())
for c in range(ct):
	n = int(input())
	li = [int(i) for i in input().split()]
	op = [0 for i in range(n)]
	for i in range(1, n + 1):
		pos = li.index(i)
		for j in range(pos - 1, -1, -1):
			if op[j] == 0 and li[j] > li[j + 1]:
				op[j] = 1
				(li[j], li[j + 1]) = (li[j + 1], li[j])
			else:
				break
	print(*li)


import sys
input = sys.stdin.readline
out = sys.stdout

def main():
	q = int(input())
	for _ in range(q):
		n = int(input())
		arr = list(map(int, input().split()))
		k = n - 1
		used = set()
		for i in range(n - 1):
			pos = i
			for j in range(i + 1, n):
				if arr[j] < arr[pos]:
					pos = j
			for j in range(pos, i, -1):
				if j not in used:
					(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
					used.add(j)
					k -= 1
					if k == 0:
						break
			if k == 0:
				break
		print(*arr)
main()


q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	s = []
	for i in range(n - 1):
		s.append(0)
	for i in range(n):
		m = i
		for j in range(i + 1, n):
			if a[m] > a[j]:
				m = j
		for j in range(m, 0, -1):
			if s[j - 1] != 1 and a[j - 1] > a[j]:
				t = a[j - 1]
				a[j - 1] = a[j]
				a[j] = t
				s[j - 1] = 1
	for i in range(n):
		print(a[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.insert(0, 0)
	to_be_used = 1
	while to_be_used < n:
		minipos = to_be_used
		for i in range(to_be_used + 1, n + 1):
			if arr[i] < arr[minipos]:
				minipos = i
		if minipos == to_be_used:
			to_be_used += 1
		else:
			start = minipos
			while start > to_be_used:
				temp = arr[start - 1]
				arr[start - 1] = arr[start]
				arr[start] = temp
				start -= 1
			to_be_used = minipos
	for i in range(1, n):
		print(arr[i], end=' ')
	print(arr[n])


q = int(input())
for _ in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	p2 = p
	s = 1
	index = 0
	while index < n:
		if p[index] == s:
			index += 1
			if index == n:
				break
			s = min(p2[index:])
			continue
		temp = index
		index = p2.index(s)
		p2.remove(s)
		p2.insert(temp, s)
		s = min(p2[index:])
	print(*p2)


for _ in range(int(input())):
	n = int(input())
	p = [int(__) for __ in input().split()]
	i = 0
	while i < n - 1:
		shit = p.index(min(p[i:]))
		p = p[:i] + [p[shit]] + p[i:shit] + p[shit + 1:]
		if i == shit:
			i += 1
		else:
			i = shit
	for i in p:
		print(i, end=' ')
	print('')


for kk in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l22 = l.copy()
	l22.sort()
	k = 0
	ans = []
	while k < n - 1:
		curr = min(l)
		if curr == n:
			break
		index = 0
		for i in l:
			if i == curr:
				break
			index += 1
		if index + k <= n - 1:
			l = [l[index]] + l[:index] + l[index + 1:]
			k += index
		else:
			index2 = n - 1 - k
			l = l[:index - index2] + [l[index]] + l[index - index2:index] + l[index + 1:]
			k += index2
		curr += 1
		if index == 0:
			index += 1
		ans.extend(l[:index])
		l = l[index:]
		if l == []:
			break
	ans.extend(l)
	s = ''
	for i in ans:
		s += str(i) + ' '
	print(s[:-1])


def solve(arr, swaps):
	if swaps == 0 or arr == []:
		return arr
	if len(arr) == 1:
		return arr
	else:
		min_index = arr.index(min(arr[1:1 + swaps]))
		element = arr[min_index]
		if arr[0] < element:
			return [arr[0]] + solve(arr[1:], swaps)
		swaps = swaps - min_index
		element = arr.pop(min_index)
		new_arr = [element] + arr
		return new_arr[:min_index] + solve(new_arr[min_index:], swaps)
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [int(s) for s in input().split()]
	ansArr = solve(arr, n - 1)
	print(*ansArr)


import sys
for i in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().rstrip().split()))
	a = []
	for i in range(1, n + 1):
		if l == []:
			break
		if i in l:
			w = l.index(i)
			if w == 0:
				a.append(i)
				l = l[1:]
			else:
				a.append(i)
				a += l[0:w - 1]
				l = [l[w - 1]] + l[w + 1:]
	print(' '.join((str(i) for i in a)))


t = int(input())
for w in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	i = 0
	while i < n:
		j = l.index(min(l[i:]))
		if j == i:
			i += 1
		else:
			for k in range(j, i, -1):
				(l[k], l[k - 1]) = (l[k - 1], l[k])
			i = j
	print(*l)


q = int(input())
for counter in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = n - 1
	p = 0
	ans = ''
	while m > 0 and a:
		el = min(a[0:m + 1])
		index = a.index(el)
		if index == 0:
			ans += str(a[0]) + ' '
			del a[0]
			m -= 1
		else:
			a.remove(el)
			ans += str(el) + ' '
			for i in range(index - 1):
				ans += str(a[i]) + ' '
			del a[0:index - 1]
			m -= index - 1
	if a:
		ans += str(a[0])
	print(ans)


q = int(input())
for i in range(q):
	n = int(input())
	lst = list(map(int, input().split()))
	l = 0
	r = n - 1
	for j in range(1, n):
		r = lst.index(j)
		if r > l:
			d = lst[0:l]
			a = lst[l:r]
			b = [lst[r]]
			c = lst[r + 1:]
			newlst = d + b + a + c
			lst = newlst
			l = r
		elif r == l:
			l = r + 1
	for j in lst:
		print(j, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l1 = [1] * (n - 1)
	l = list(map(int, input().split()))
	for i in range(n):
		for j in range(n - 2, -1, -1):
			if l[j] > l[j + 1] and l1[j] == 1:
				t = l[j]
				l[j] = l[j + 1]
				l[j + 1] = t
				l1[j] = 0
	for i in range(n):
		print(l[i], end=' ')
	print()


import sys
import math
import itertools
import collections

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return int(str(n)[::-1])

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base=3):
	newnumber = ''
	while number > 0:
		newnumber = str(number % base) + newnumber
		number //= base
	return newnumber

def ideal(arr, n):
	if arr == [i for i in range(1, n + 1)]:
		return True
	else:
		return False
t = ii()
for _ in range(t):
	n = ii()
	p = li()
	i = 1
	e = 1
	s = set()
	while i < n and (not ideal(p, n)) and (e < n + 1):
		pos = p.index(e)
		for j in range(pos, e - 1, -1):
			if j not in s:
				s.add(j)
				if p[j] < p[j - 1]:
					(p[j], p[j - 1]) = (p[j - 1], p[j])
				i += 1
				if i == n or ideal(p, n):
					break
			else:
				continue
		e += 1
	print(wr(p))


def f(a):
	n = len(a)
	vis = set()
	for i in range(n - 1, 0, -1):
		if a[i] < a[i - 1]:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
			vis.add(i - 1)
	for i in range(0, n - 1):
		if i not in vis:
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	return a
for _ in range(int(input())):
	a = input()
	l = list(map(int, input().strip().split()))
	print(*f(l))


import sys
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	used = [False] * (n - 1)
	while True:
		noChanges = True
		for i in reversed(range(n - 1)):
			if not used[i] and a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				used[i] = True
				noChanges = False
		if noChanges:
			break
	print(*a)


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = []
	for i in range(n - 2, -1, -1):
		if li[i] > li[i + 1]:
			(li[i], li[i + 1]) = (li[i + 1], li[i])
			ans.append(i)
	for i in range(0, n - 1):
		if i not in ans and li[i] > li[i + 1]:
			(li[i], li[i + 1]) = (li[i + 1], li[i])
	print(*li)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	bol = [True for i in range(n)]
	flag = True
	while flag:
		flag = False
		for i in range(n - 1):
			if arr[n - i - 1] < arr[n - i - 2] and bol[n - i - 1]:
				bol[n - i - 1] = False
				tmp = arr[n - i - 1]
				arr[n - i - 1] = arr[n - i - 2]
				arr[n - i - 2] = tmp
				flag = True
	for x in range(n):
		if x > 0:
			print(' ', end='')
		print(arr[x], end='')
	print()


def find_num(array, num):
	for i in range(len(array)):
		if array[i] == num:
			return i
amount = int(input())
for i in range(amount):
	n = int(input())
	array = [int(s) for s in input().split()]
	used = [0] * (n - 1)
	for j in range(1, n + 1):
		curr = find_num(array, j)
		for k in range(curr, 0, -1):
			if not used[k - 1] and j < array[k - 1]:
				(array[k], array[k - 1]) = (array[k - 1], array[k])
				used[k - 1] = 1
	print(' '.join([str(s) for s in array]))


def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
q = int(input())
for _ in range(q):
	n = int(input())
	a = [int(x) for x in input().split()]
	used = set()
	for __ in range(n - 1):
		for i in range(n - 2, -1, -1):
			if i not in used and a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				used.add(i)
	oneLineArrayPrint(a)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	sin = 0
	while sin < n - 1:
		m = min(l[sin:])
		idx = l.index(m)
		l1 = l[0:sin] + [m] + l[sin:idx]
		if idx + 1 < n:
			l1 += l[idx + 1:]
		l = l1
		if idx == sin:
			sin = idx + 1
		else:
			sin = idx
	for e in l:
		print(e, end=' ')
	print()


import sys
input = sys.stdin.buffer.readline
from collections import defaultdict

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

def main():
	Q = int(input())
	for i in range(Q):
		N = int(input())
		a = getlist()
		ans = []
		left = 0
		for j in range(1, N + 1):
			for k in range(len(a)):
				if a[k] == j:
					if k > 0:
						ans += [j] + a[:k - 1]
					else:
						ans += [a[0]]
					if k > 0:
						a = [a[k - 1]] + a[k + 1:]
					else:
						a = a[1:]
					break
		ans = list(map(str, ans))
		print(' '.join(ans))
main()


q = int(input())
while q:
	n = int(input())
	arr = [int(i) for i in input().split()]
	rem = [1] * n
	for i in range(n - 1, 1, -1):
		if arr[i] < arr[i - 1]:
			rem[i] = 0
			(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
	change = 1
	while change == 1:
		change = 0
		for i in range(n - 1, 0, -1):
			if arr[i] < arr[i - 1] and rem[i] == 1:
				rem[i] = 0
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
				change = 1
	print(*arr)
	q -= 1


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))

	def findMin(arr):
		mn = 101
		for i in range(len(arr)):
			if mn > arr[i]:
				mn = arr[i]
				ind = i
		return ind

	def swap(a, i):
		tmp = a[i]
		a[i] = a[i + 1]
		a[i + 1] = tmp

	def perm(a):
		if a == []:
			return []
		ind = findMin(a)
		if ind == 0:
			return [a[0]] + perm(a[ind + 1:])
		for i in range(ind - 1, -1, -1):
			swap(a, i)
		next = perm(a[ind:])
		return a[:ind] + next
	print(*perm(a))


for q in range(int(input())):
	n = int(input())
	a = [int(x) - 1 for x in input().split()]
	pos = 0
	while pos < n:
		nxt = a.index(min(a[pos:]))
		el = a[nxt]
		del a[nxt]
		a.insert(pos, el)
		if pos == nxt:
			pos += 1
		else:
			pos = nxt
	print(*[x + 1 for x in a])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	b = a
	i = 0
	p = 0
	while i < n:
		i = a.index(min(b))
		if i != p:
			for j in range(i - 1, p - 1, -1):
				(a[j + 1], a[j]) = (a[j], a[j + 1])
		if i == p:
			b = a[i + 1:]
			p = i + 1
			if len(b) <= 1:
				break
			continue
		b = a[i:]
		p = i
		if len(b) == 1:
			break
	print(*a)


def line():
	return map(int, input().split())

def num():
	return int(input())
from itertools import repeat
Q = num()
for _ in repeat(None, Q):
	n = num()
	a = list(line())
	q = 0
	w = 1
	while q < n - 1:
		e = a.index(w, q)
		if e != q:
			del a[e]
			a.insert(q, w)
			q = e
		else:
			q = e + 1
		w = min(a[q:], default=n)
	print(' '.join(map(str, a)))


def permutations(n, arr):
	pos = 0
	for j in range(1, n):
		if pos == n - 1:
			break
		i = arr.index(j)
		if i == pos:
			pos += 1
		elif i > pos:
			arr.insert(pos, arr.pop(i))
			pos = i
	return arr
q = int(input())
for _ in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*permutations(n, arr))


def bringToCorrect(arr, s, ind, i):
	while arr[ind] < arr[ind - 1]:
		if ind + 1 in s:
			s.remove(ind + 1)
		else:
			break
		temp = arr[ind]
		arr[ind] = arr[ind - 1]
		arr[ind - 1] = temp
		ind -= 1
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	s = [i for i in range(2, n + 1)]
	s = set(s)
	for i in range(1, n + 1):
		if arr[i - 1] == i:
			continue
		else:
			ind = 0
			while arr[ind] != i:
				ind += 1
			bringToCorrect(arr, s, ind, i)
	print(*arr)


q = int(input())

def turn(l):
	if len(l) == 1:
		return l
	if len(l) == 2:
		return [min(l), max(l)]
	m = min(l)
	i1 = l.index(m)
	if i1 == 0:
		return [m] + turn(l[1:])
	return [m] + l[:i1 - 1] + turn([l[i1 - 1]] + l[i1 + 1:])
for i in range(0, q):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = turn(l)
	for i in l1:
		print(i, end=' ')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	i = 0
	while len(a) > 1:
		i = a.index(min(a))
		if a[0] == a[i]:
			ans.append(a[0])
			a.pop(0)
		else:
			ans.append(a[i])
			ans.extend(a[:i - 1])
			a = [a[i - 1]] + a[i + 1:]
	if len(ans) < n:
		ans.append(a[0])
	print(*ans)


n = int(input())
for i in range(n):
	length = int(input())
	s = set(list(range(1, length + 1)))
	li = [int(x) for x in input().split(' ')]
	k = 0
	while k < length - 1:
		nextIndex = li.index(min(s))
		if nextIndex == k:
			s.remove(li[k])
			k += 1
		else:
			temp = li[nextIndex]
			for i in range(k, nextIndex + 1):
				s.remove(li[i])
			li[k + 1:nextIndex + 1] = li[k:nextIndex]
			li[k] = temp
			k = nextIndex
			s.add(li[nextIndex])
	print(*li)


t = int(input())
for _ in range(t):
	n = int(input())
	s = set((i for i in range(1, n + 1)))
	l = list(map(int, input().split()))
	prev_ind = 0
	while prev_ind != n - 1:
		ind = l.index(min(s))
		s.remove(l[ind])
		for i in range(ind - prev_ind):
			if l[ind - i] < l[ind - i - 1]:
				(l[ind - i], l[ind - i - 1]) = (l[ind - i - 1], l[ind - i])
				if i != 0 and l[ind - i] in s:
					s.remove(l[ind - i])
		prev_ind = ind
	print(' '.join(list(map(str, l))))


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in range(1, n + 1):
		d[i] = 0
	for i in range(len(a)):
		d[a[i]] = i
	x = 0
	for k in d:
		if d[k] > x:
			if k < a[x]:
				a = a[:x] + [k] + a[x:d[k]] + a[d[k] + 1:]
				x = d[k]
			else:
				a = a[:x] + [k] + a[x:d[k]] + a[d[k] + 1:]
				(a[x], a[x + 1]) = (a[x + 1], a[x])
				x = d[k]
		elif d[k] == x:
			x += 1
	print(*a)


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from io import BytesIO, IOBase
from itertools import *
from collections import *
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a

def interact(type, x):
	if type == 'r':
		inp = input()
		return inp.strip()
	else:
		print(x, flush=True)

def findTrailingZeros(n):
	count = 0
	while n >= 5:
		n //= 5
		count += n
	return count

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
res = set()

def solven(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solven(p * 10 + a, l + 1, a, b, n)
	solven(p * 10 + b, l + 1, a, b, n)

def subsetsUtil(A, subset, index, d):
	print(*subset)
	s = sum(subset)
	d.append(s)
	for i in range(index, len(A)):
		subset.append(A[i])
		subsetsUtil(A, subset, i + 1, d)
		subset.pop(-1)
	return d

def subsetSums(arr, l, r, d, sum=0):
	if l > r:
		d.append(sum)
		return
	subsetSums(arr, l + 1, r, d, sum + arr[l])
	subsetSums(arr, l + 1, r, d, sum)
	return d

def print_factors(x):
	factors = []
	for i in range(1, x + 1):
		if x % i == 0:
			factors.append(i)
	return factors

def calc(X, d, ans, D):
	if len(X) == 0:
		return
	i = X.index(max(X))
	ans[D[max(X)]] = d
	Y = X[:i]
	Z = X[i + 1:]
	calc(Y, d + 1, ans, D)
	calc(Z, d + 1, ans, D)

def main():
	t = inpu()
	for _ in range(t):
		n = inpu()
		arr = lis()
		i = k = 0
		while k < len(arr):
			k += 1
			j = arr.index(k)
			if j >= i:
				arr.insert(i, arr.pop(j))
				if i == j:
					i = i + 1
				else:
					i = j
		print(*arr)
main()


q = int(input())
for _ in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	pos = 0
	for i in range(n):
		try:
			nxt = a.index(i + 1, pos)
			if nxt == pos:
				pos += 1
				continue
			for k in range(nxt - 1, pos - 1, -1):
				(a[k], a[k + 1]) = (a[k + 1], a[k])
			pos = nxt
		except ValueError:
			pass
	print(*a)


q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	steps = n - 1
	i1 = 0
	while steps > 0 and i1 < n:
		r = l.index(min(l[i1:i1 + steps + 1]))
		if r == i1:
			i1 = i1 + 1
			continue
		elif steps >= r - i1:
			for j in range(r, i1, -1):
				(l[j], l[j - 1]) = (l[j - 1], l[j])
			steps = steps - (r - i1)
		else:
			break
		i1 = r
	print(*l)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	for i in range(n):
		l[i] -= 1
	pos = 0
	while pos < n:
		nxt = l.index(min(l, key=lambda x: x if l.index(x) >= pos else n))
		ele = l[nxt]
		l.pop(nxt)
		l.insert(pos, ele)
		if pos == nxt:
			pos = nxt + 1
		else:
			pos = nxt
	for i in l:
		print(i + 1, end=' ')
	print()


from sys import stdin
input = stdin.buffer.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	i = 0
	res = []
	while i < n:
		m = min(arr[i:])
		j = arr.index(m)
		x = arr[j]
		if len(res) > 0:
			if res[-1] > arr[j]:
				temp = res[-1]
				res[-1] = arr[j]
				x = temp
		res = res + [x] + arr[i:j]
		i = j + 1
	print(*res)


q = int(input())
for _ in range(q):
	n = int(input())
	data = list(map(int, input().split()))
	start = 0
	index = data.index(min(data))
	while index < n:
		data = data[:start] + [data[index]] + data[start:index] + data[index + 1:]
		was = start == index
		start = index + was
		if index != n - 1:
			tmp = data[index + was:]
			index += tmp.index(min(tmp)) + was
		else:
			index = n
	print(*data, end='\n')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mark = [0] * n
	x = 1
	done = 0
	barrier = 0
	while done < n - 1 and x <= n:
		i = l.index(x)
		for j in range(i - 1, x - 2, -1):
			if mark[j] == 0 and l[j] > l[j + 1]:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				done += 1
				mark[j] = 1
			else:
				break
			if done >= n - 1:
				break
		x += 1
	print(*l)


from math import ceil, sqrt, gcd
from collections import deque

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
t = ii()
while t:
	t -= 1
	n = ii()
	a = li()
	p = 0
	ma = 1000
	k = -1
	while p != n - 1:
		ma = 1000
		k = -1
		for i in range(p, n):
			if a[i] < ma:
				k = i
				ma = a[i]
		if k == p:
			p += 1
			continue
		if k == -1:
			break
		m1 = a[k]
		for i in range(k - 1, p - 1, -1):
			a[i + 1] = a[i]
		a[p] = m1
		p = k
	print(*a)


from math import *
from collections import *
t = int(input())
for y in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ct = n - 1
	i = 1
	prev = -1
	while ct != 0 and i <= n:
		x = a.index(i)
		for j in range(x, max(i - 1, prev), -1):
			if a[j] < a[j - 1]:
				(a[j - 1], a[j]) = (a[j], a[j - 1])
				ct -= 1
			if ct == 0:
				break
		i += 1
		prev = max(prev, x)
	for i in a:
		print(i, end=' ')
	print()


q = int(input())
for i in range(q):
	n = int(input())
	a = list((int(j) for j in input().split()))
	used = [False] * n
	for k in range(1, n):
		s = a.index(k)
		while s != k - 1 and used[s - 1] == False and (a[s - 1] > a[s]):
			used[s - 1] = True
			(a[s - 1], a[s]) = (a[s], a[s - 1])
			s -= 1
	for l in a:
		print(l, end=' ')
	print()


q = int(input())
while q:
	n = int(input())
	m = list(map(int, input().split()))
	cnt = n - 1
	used = [0] * n
	i = 0
	while i < n:
		ch = m[i]
		mi = ch
		xi = 1000
		for j in range(i + 1, min(n, i + cnt + 1)):
			if m[j] < mi:
				mi = m[j]
				xi = j
		if mi != ch:
			del m[xi]
			m.insert(i, mi)
			cnt -= xi - i
			i = xi
		else:
			i += 1
	print(*m)
	q -= 1


qq = int(input())
for q in range(qq):
	n = int(input())
	dat = list(map(int, input().split()))
	already = [False] * 110
	for j in range(0, n - 1):
		ma = 99999
		maindex = 99999
		for i in range(0, n - 1):
			if already[i]:
				continue
			if dat[i] < dat[i + 1]:
				continue
			if dat[i + 1] < ma:
				if dat[i + 1] == n:
					continue
				maindex = i
				ma = dat[i + 1]
		if maindex == 99999:
			break
		else:
			already[maindex] = True
			(dat[maindex], dat[maindex + 1]) = (dat[maindex + 1], dat[maindex])
	dat = list(map(lambda x: str(x), dat))
	print(' '.join(dat))


def movearray(start, end, positons, perms):
	for j in range(end - 1, start - 1, -1):
		(a, b) = (positions[perms[j]], positions[perms[j + 1]])
		(positions[perms[j + 1]], positions[perms[j]]) = (a, b)
		(a, b) = (perms[j], perms[j + 1])
		(perms[j + 1], perms[j]) = (a, b)
q = int(input())
for i in range(q):
	n = int(input())
	positions = [0] * (n + 1)
	new = list(map(int, input().split(' ')))
	perms = []
	perms.append(0)
	perms = perms + new
	for j in range(1, n + 1):
		positions[perms[j]] = j
	end = 1
	for j in range(1, n + 1):
		index = positions[j]
		if index > end:
			movearray(end, index, positions, perms)
			end = index
		elif index == end:
			end += 1
	for j in range(1, n + 1):
		print(perms[j], end=' ')
	print()


q = int(input())

def change(s, e, l):
	return p[:s] + p[e:e + 1] + p[s:e] + p[e + 1:]
for _ in range(q):
	n = int(input())
	p = [int(x) for x in input().split()]
	v = [False] * (n + 1)
	i = 0
	s = 0
	num = 1
	while i < n:
		v[p[i]] = True
		if p[i] == num:
			if i == s:
				s += 1
				i += 1
			else:
				p = change(s, i, p)
				s = i
		else:
			i += 1
			continue
		for j in range(1, n + 1):
			if not v[j]:
				num = j
				break
		if s < n and num > p[s]:
			num = p[s]
	print(' '.join(map(str, p)))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	start = 0
	while start < n - 1:
		(mn, pos) = (arr[start], start)
		for i in range(start + 1, n):
			if arr[i] < mn:
				mn = arr[i]
				pos = i
		i = pos - 1
		while i >= start:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			i -= 1
		start = max(pos, start + 1)
	print(*arr)


def process_case():
	n = int(input())
	arr = [*map(int, input().split())]
	pos = [None] * (n + 1)
	for (i, elem) in enumerate(arr):
		pos[elem] = i
	cur_least = 1
	first_accessible_pos = 0
	while cur_least <= n and first_accessible_pos < n:
		cur_pos = pos[cur_least]
		dist = cur_pos - first_accessible_pos
		for i in range(dist):
			prev = cur_pos - i - 1
			cur = cur_pos - i
			(pos[arr[prev]], pos[arr[cur]]) = (cur, prev)
			(arr[prev], arr[cur]) = (arr[cur], arr[prev])
		if dist == 0:
			first_accessible_pos += 1
		elif dist > 0:
			first_accessible_pos = cur_pos
		cur_least += 1
	for elem in arr:
		print(elem, end=' ')
	print()
tests_count = int(input())
for _ in range(tests_count):
	process_case()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	aa = set((i for i in range(n - 1)))
	for i in range(n - 2, -1, -1):
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			aa.remove(i)
	for i in aa:
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	print(*arr)


query = int(input())
for _ in range(query):
	n = int(input())
	arr = list(map(int, input().split()))
	p = sorted(arr)
	check = [0 for i in range(n)]
	for i in range(1, n):
		ind = arr.index(i)
		if check[ind] == 0:
			for j in range(n):
				if check[j] == 0:
					break
			arr.pop(ind)
			arr.insert(j, i)
			for k in range(j, ind + 1):
				check[k] = 1
			if arr.index(i) != ind:
				check[ind] = 0
	print(*arr)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : list(map(int, input().split()))
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
for _ in range(ii()):
	n = ii()
	l = il()
	s = set()
	for j in range(100):
		for i in range(n - 1, 0, -1):
			if l[i] < l[i - 1] and (not i - 1 in s):
				s.add(i - 1)
				(l[i], l[i - 1]) = (l[i - 1], l[i])
	print(*l)


from sys import stdin
c = int(stdin.readline().strip())
pos = [-1 for i in range(200)]
for caso in range(c):
	n = int(stdin.readline().strip())
	s = list(map(int, stdin.readline().strip().split()))
	for i in range(n):
		pos[s[i]] = i
	op = 0
	vis = [False for i in range(n + 2)]
	for i in range(1, n + 1):
		while op < n - 1 and pos[i] > 0 and (s[pos[i]] < s[pos[i] - 1]) and (vis[pos[i] - 1] == False):
			vis[pos[i] - 1] = True
			op += 1
			x = s[pos[i] - 1]
			s[pos[i]] = x
			s[pos[i] - 1] = i
			pos[i] -= 1
			pos[x] += 1
	print(*s)


import sys

def main():
	solns = []
	q = int(sys.stdin.readline())
	for _ in range(q):
		n = int(sys.stdin.readline())
		arr = [int(x) for x in sys.stdin.readline().split(' ')]
		left = 0
		while left <= n - 1:
			minIdx = arr[left:].index(min(arr[left:])) + left
			if minIdx == left:
				left += 1
				continue
			for idx in range(minIdx, left, -1):
				tmp = arr[idx]
				arr[idx] = arr[idx - 1]
				arr[idx - 1] = tmp
			left = minIdx
		solns.append(arr)
	print('\n'.join([' '.join((str(a) for a in x)) for x in solns]))
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	idx = 0
	while idx < n - 1:
		(m, mi) = (a[idx], idx)
		for j in range(idx, n):
			if a[j] < m:
				m = a[j]
				mi = j
		a = a[:idx] + [a[mi]] + a[idx:mi] + a[mi + 1:]
		idx = mi + (idx == mi)
	print(*a)


from sys import stdin
splInp = lambda : stdin.readline().split()
for q in range(int(input())):
	n = int(input())
	p = [int(x) for x in splInp()]
	q = [True for i in range(n)]
	for i in range(n - 1, 0, -1):
		if p[i - 1] > p[i]:
			(p[i - 1], p[i]) = (p[i], p[i - 1])
			q[i] = False
	for i in range(1, n):
		if q[i] and p[i - 1] > p[i]:
			(p[i - 1], p[i]) = (p[i], p[i - 1])
	print(*p)


q = int(input().strip())
for _ in range(q):
	n = int(input().strip())
	per = [int(i) for i in input().strip().split()]
	has_op = [0 for i in range(n)]
	min_val = 1
	while min_val < n:
		for i in range(n):
			min_in = i
			if per[min_in] == min_val and i > 0:
				for j in range(i - 1, -1, -1):
					if has_op[j] == 0 and per[min_in] < per[j]:
						temp = per[j]
						per[j] = per[min_in]
						per[min_in] = temp
						has_op[j] = 1
						min_in -= 1
					else:
						break
				break
		min_val += 1
	print(' '.join((str(k) for k in per)))


cases = int(input())
for q in range(cases):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)[::-1]
	f = 0
	v = b.pop()
	pos = a.index(v)
	c = 0
	d = {(i, j): True for i in range(n) for j in range(n)}
	while c < n - 1 and b:
		while c < n - 1 and pos > 0 and (v < a[pos - 1]):
			if d[pos, pos - 1]:
				d[pos, pos - 1] = False
				(a[pos - 1], a[pos]) = (v, a[pos - 1])
				pos -= 1
				c += 1
			else:
				break
		v = b.pop()
		pos = a.index(v)
	print(*a)


for _ in range(int(input())):
	n = int(input())
	_input = input().split()
	A = []
	for elems in _input:
		A.append(int(elems))
	mx = 0
	for num in range(1, n + 1):
		i = A.index(num)
		if i > mx:
			for j in range(A.index(num), mx, -1):
				if A[j] < A[j - 1]:
					(A[j], A[j - 1]) = (A[j - 1], A[j])
			mx = i
	for elem in A:
		print(elem, end=' ')


from sys import stdin, stdout
import bisect
import math

def st():
	return list(stdin.readline().strip())

def inp():
	return int(stdin.readline())

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

def mp():
	return map(int, stdin.readline().split())

def pr(n):
	stdout.write(str(n) + '\n')

def soe(limit):
	l = [1] * (limit + 1)
	prime = []
	for i in range(2, limit + 1):
		if l[i]:
			for j in range(i * i, limit + 1, i):
				l[j] = 0
	for i in range(2, limit + 1):
		if l[i]:
			prime.append(i)
	return prime

def segsoe(low, high):
	limit = int(high ** 0.5) + 1
	prime = soe(limit)
	n = high - low + 1
	l = [0] * (n + 1)
	for i in range(len(prime)):
		lowlimit = low // prime[i] * prime[i]
		if lowlimit < low:
			lowlimit += prime[i]
		if lowlimit == prime[i]:
			lowlimit += prime[i]
		for j in range(lowlimit, high + 1, prime[i]):
			l[j - low] = 1
	for i in range(low, high + 1):
		if not l[i - low]:
			if i != 1:
				print(i)

def gcd(a, b):
	while b:
		a = a % b
		(b, a) = (a, b)
	return a

def power(a, n):
	r = 1
	while n:
		if n & 1:
			r = r * a
		a *= a
		n = n >> 1
	return r

def solve():
	n = inp()
	l = li()
	d = {}
	for i in range(n):
		d[l[i]] = i
	x = 1
	p = [0] * n
	c = 0
	while x <= n and c <= n - 1:
		a = d[x]
		for j in range(a - 1, -1, -1):
			if l[j] > x and p[j] == 0:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				c += 1
				p[j] = 1
			else:
				break
		x += 1
		i += 1
	print(*l)
for _ in range(inp()):
	solve()


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	i = n - 1
	g = [1] * (n - 1)
	for j in range(n):
		for i in range(n - 1, j, -1):
			if s[i] < s[i - 1] and g[i - 1]:
				(s[i], s[i - 1]) = (s[i - 1], s[i])
				g[i - 1] = 0
	print(*s)


from collections import *
import sys

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))
t = ri()
for _ in range(t):
	n = ri()
	p = rl()
	p = [x - 1 for x in p]
	move_done = [1] + [0] * (n - 1)
	pos = [-1] * n
	for i in range(n):
		pos[p[i]] = i
	i = 0
	while i < n:
		if pos[i] == 0:
			i += 1
		else:
			left = p[pos[i] - 1]
			if left > i and move_done[pos[i]] == 0:
				move_done[pos[i]] = 1
				temp = pos[i]
				pos[i] = pos[left]
				pos[left] = temp
				p[pos[i]] = i
				p[pos[left]] = left
			else:
				i += 1
	q = [x + 1 for x in p]
	print(*q)


def main():
	for _ in range(int(input())):
		(_, l, buf) = (input(), list(map(int, input().split())), [])
		while len(l) > 1:
			i = min(range(len(l)), key=l.__getitem__)
			buf.append(l[i])
			if i:
				buf += l[:i - 1]
				l = [l[i - 1], *l[i + 1:]]
			else:
				del l[0]
		buf.append(l[0])
		print(*buf)
main()


t = int(input())
while t > 0:
	n = int(input())
	arr = [int(i) for i in input().split()]
	st = 0
	if arr == sorted(arr):
		print(*arr)
	else:
		num = 1
		prev = -1
		index = 0
		while st <= n - 1:
			k = arr.index(num)
			if k != index:
				for i in range(k - 1, prev, -1):
					st += 1
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				if len(arr[k:]) <= 1:
					break
				prev = k - 1
				index = k
				num = min(arr[k:])
			else:
				if len(arr[k + 1:]) <= 1:
					break
				num = min(arr[k + 1:])
				prev = k
				index = k + 1
		print(*arr)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	perform = [0 for i in range(n)]
	rec = [0 for i in range(n)]
	for i in range(n):
		rec[s[i] - 1] = i
	op = n - 1
	for i in range(n):
		if op == 0:
			break
		p = rec[i] - 1
		temp = op
		tempP = p
		lim = p + 1
		while tempP >= 0 and temp > 0:
			if perform[tempP] == 1:
				break
			if s[tempP] > i + 1 and perform[p] == 0:
				lim = tempP
			tempP -= 1
			temp -= 1
		while p >= lim and op > 0:
			rec[i] = p
			(s[p], s[p + 1]) = (s[p + 1], s[p])
			perform[p] = 1
			rec[s[p + 1] - 1] = p + 1
			p -= 1
			op -= 1
	for i in s:
		print(i, end=' ')
	print('')


from sys import stdin, stdout
from collections import defaultdict

def swap(A, d, x, y):
	t = A[x]
	A[x] = A[y]
	A[y] = t
	d[A[x]] = x
	d[A[y]] = y
	return (A, d)

def solve():
	n = int(input())
	A = [int(i) for i in stdin.readline().split()]
	d = defaultdict()
	st = set()
	for i in range(len(A)):
		d[A[i]] = i
	for i in range(len(A) - 1):
		while True:
			if d[i + 1] == 0:
				break
			if A[d[i + 1] - 1] > A[d[i + 1]] and d[i + 1] - 1 not in st:
				st.add(d[i + 1] - 1)
				(A, d) = swap(A, d, d[i + 1] - 1, d[i + 1])
			else:
				break
	for i in A:
		print(str(i) + ' ', end='')
	print()
	return 0
t = int(input())
for i in range(t):
	solve()


t = int(input())
for r in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	visited = [0] * (n - 1)
	for k in range(n - 1):
		pos = -1
		maxi = -1
		maxnum = 10000
		for i in range(n - 1):
			if visited[i] == 0:
				if l[i] > l[i + 1]:
					if l[i + 1] < maxnum:
						maxnum = l[i + 1]
						pos = i
		if pos != -1:
			visited[pos] = 1
			temp = l[pos]
			l[pos] = l[pos + 1]
			l[pos + 1] = temp
	for i in l:
		print(i, end=' ')
	print()


import sys

def solve():
	(n,) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	was = set()
	for value in range(1, n + 1):
		index = a.index(value)
		while index > 0 and a[index] < a[index - 1] and (index not in was):
			if index > 0 and a[index] < a[index - 1] and (index not in was):
				was.add(index)
				(a[index], a[index - 1]) = (a[index - 1], a[index])
			index -= 1
	print(*a)
(q,) = map(int, sys.stdin.readline().split())
for _ in range(q):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = set()
	pos = n - 2
	ops = 0
	while pos > -1:
		if a[pos] > a[pos + 1]:
			s.add(str(pos) + str(pos + 1))
			(a[pos], a[pos + 1]) = (a[pos + 1], a[pos])
			ops += 1
		pos -= 1
	for i in range(1, len(a)):
		if a[i] < a[i - 1] and str(i - 1) + str(i) not in s and (ops < n - 1):
			(a[i], a[i - 1]) = (a[i - 1], a[i])
			ops += 1
	print(*a)


def find_min_index(a, start):
	if start >= len(a):
		return -1
	m = min(a[start:])
	for i in range(start, len(a)):
		if a[i] == m:
			return i
	return -1
q = int(input())
for qi in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	while i != -1:
		min_index = find_min_index(l, i)
		if min_index == i:
			i += 1
			continue
		if min_index == -1:
			break
		min_val = l[min_index]
		for j in reversed(range(i + 1, min_index + 1)):
			l[j] = l[j - 1]
		l[i] = min_val
		i = min_index
	for e in l:
		print(e, end=' ')
	print()


mod = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
import bisect
from bisect import bisect_left as bl
from bisect import bisect_right as br
import itertools
import collections
import math
import heapq
import random

def modinv(n, p):
	return pow(n, p - 2, p)

def ncr(n, r, p):
	t = fact[n] * (ifact[r] * ifact[n - r] % p) % p
	return t

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

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

def main():
	t = inin()
	for _ in range(t):
		n = inin()
		a = ain()
		i = 0
		y = n - 1
		x = 0
		while i < n:
			for k in range(x, n):
				j = a.index(k + 1)
				if j - i <= n - 1 and j - i > 0 and (a[j] < a[i]):
					a.pop(j)
					a.insert(i, k + 1)
					i = j - 1
					break
			i += 1
			x += 1
		print(*a)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


def get_min(l, r, A):
	mn = A[l]
	ans = l
	for i in range(l, r):
		s = A[i]
		if s < mn:
			mn = s
			ans = i
	return ans

def solve(A, n):
	l = 0
	r = n
	while l != n:
		j = get_min(l, r, A)
		for k in range(j, l, -1):
			(A[k], A[k - 1]) = (A[k - 1], A[k])
		l = max(j, l + 1)
q = int(input())
for i in range(q):
	n = int(input())
	A = [int(i) for i in input().split()]
	solve(A, n)
	print(' '.join(map(str, A)))


q = int(input())
for rwere in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	ope = n - 1
	miejsce = 0
	while ope > 0:
		if miejsce > n - 1:
			break
		bestie = 10000000000
		best_miejsce = -1
		for i in range(miejsce, min(n, ope + miejsce + 1)):
			if l[i] < bestie:
				bestie = l[i]
				best_miejsce = i
		t = best_miejsce
		if t != -1:
			while t > miejsce:
				a = l[t]
				b = l[t - 1]
				l[t - 1] = a
				l[t] = b
				t -= 1
				ope -= 1
		miejsce = max(best_miejsce, miejsce + 1)
	print(*l)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	while i < n - 1:
		m = min(l[i:])
		i_d = l.index(m)
		if i == i_d:
			i += 1
		else:
			l[i:i_d + 1] = [m] + l[i:i_d]
			i = i_d
	print(*l)


__version__ = '2.2'
__date__ = '2019-11-20'
import sys

def solve(n, perm):
	curr = 0
	for i in range(1, n):
		idx = perm.index(i)
		if curr >= idx:
			curr = max(curr, idx + 1)
		else:
			perm[curr:idx + 1] = [i] + perm[curr:idx]
			curr = idx
		if curr >= n - 1:
			break
	return perm

def main(argv=None):
	q = int(input())
	for each in range(q):
		n = int(input())
		perm = list(map(int, input().split()))
		print(' '.join(map(str, solve(n, perm))))
	return 0
STATUS = main()
sys.exit(STATUS)


q = int(input())
for qi in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	used = [False] * n
	for t in range(n):
		for i in range(len(a) - 1, 0, -1):
			if used[i]:
				continue
			if a[i] < a[i - 1]:
				(a[i], a[i - 1]) = (a[i - 1], a[i])
				used[i] = True
	print(' '.join((str(x) for x in a)))


from sys import stdin
q = int(stdin.readline().strip())

def solve(a):
	index = None
	a_sorted = sorted(a)
	for i in range(len(a)):
		if a[i] != a_sorted[i]:
			index = i
			break
	if index is None:
		return a
	real_index = a.index(a_sorted[index])
	return a[0:index] + [a_sorted[index]] + a[index:real_index - 1] + solve([a[real_index - 1]] + a[real_index + 1:])
for _ in range(q):
	n = int(stdin.readline().strip())
	a = [int(i) for i in stdin.readline().strip().split()]
	print(' '.join((str(i) for i in solve(a))))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	pos = 0
	for j in range(n):
		x = l.index(min(l[j:]))
		temp = pos
		if pos < x:
			val = l[x]
			for k in range(x, temp, -1):
				l[k] = l[k - 1]
			l[temp] = val
			pos = x
		elif pos == x:
			pos += 1
	print(*l)


q = int(input())
for _ in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	j = 0
	while i < n - 1:
		m = min(l[i:])
		i = l.index(m)
		l = l[:j] + [m] + l[j:i] + l[i + 1:]
		if i == j:
			i += 1
		j = i
	print(*l)


q = int(input())
for _ in q * ' ':
	n = int(input())
	(*s,) = map(int, input().split())
	while len(s) > 1:
		m = min(s)
		print(m, end=' ')
		i = 0
		if s[i] == m:
			s = s[1:]
		else:
			while i < len(s) - 1 and m != s[i + 1]:
				print(s[i], end=' ')
				i += 1
			s = [s[i]] + s[i + 2:]
	print(s[0])


def perturbation(task, target):
	for i in task:
		(target[i], target[i + 1]) = (target[i + 1], target[i])
	return target
q = int(input())
bunch = []
for i in range(q):
	trash = input()
	bunch.append(list(map(int, input().split())))
ans = []
for target in bunch:
	task = []
	index = []
	trig = 1
	for i in range(len(target)):
		a = target.index(i + 1)
		if len(task) == 0 and i == 0:
			for i in range(a - 1, -1, -1):
				task.append(i)
			index.append(a)
			pass
		elif a > index[-1]:
			if i + 1 < target[index[-1] - trig] and index[-1] != 0:
				for i in range(a - 1, index[-1] - 1, -1):
					task.append(i)
				if len(range(a - 1, index[-1] - 1, -1)) > 1:
					trig = 1
				else:
					trig += 1
			else:
				for i in range(a - 1, index[-1], -1):
					task.append(i)
				trig = 1
			index.append(a)
			pass
		else:
			pass
	ans.append(perturbation(task, target))
for i in ans:
	for j in i:
		print(str(j), end=' ')
	print()


def rint():
	return int(input())

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

def minimize(p):
	if len(p) <= 1:
		return p
	m = min(p)
	i = p.index(m)
	if i == 0:
		return [m] + minimize(p[1:])
	p = [m] + p[:i] + p[i + 1:]
	return p[:i] + minimize(p[i:])
q = rint()
for _ in range(q):
	n = rint()
	p = rints()
	print(*minimize(p))