B. Минимизация перестановки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка длины $$$n$$$. Напомним, что перестановкой является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2, 3, 1, 5, 4]$$$ — перестановка, но $$$[1, 2, 2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1, 3, 4]$$$ тоже не перестановка ($$$n=3$$$ но в массиве встречается $$$4$$$).

Вы можете применить максимум $$$n-1$$$ операцию к заданной перестановке (возможно, что вы не будете совершать никаких операций). $$$i$$$-я операция позволяет вам поменять местами элементы заданной перестановки на позициях $$$i$$$ и $$$i+1$$$. Каждая операция может быть применена не больше одного раза. Операции могут быть применены в произвольном порядке.

Вы можете увидеть определение лексикографического сравнения в секции примечаний.

Ваша задача — найти лексикографически минимальную перестановку, которая может быть получена с помощью применения каких-либо из данных операций в каком-либо порядке.

Вам необходимо ответить на $$$q$$$ независимых наборов входных данных.

Например, рассмотрим перестановку $$$[5, 4, 1, 3, 2]$$$. Минимальная возможная перестановка, которую мы можем получить — $$$[1, 5, 2, 4, 3]$$$, и мы можем сделать это следующим образом:

  1. выполним вторую операцию (поменяем местами второй и третий элементы) и получим перестановку $$$[5, 1, 4, 3, 2]$$$;
  2. выполним четвертую операцию (поменяем местами четвертый и пятый элементы) и получим перестановку $$$[5, 1, 4, 2, 3]$$$;
  3. выполним третью операцию (поменяем местами третий и четвертый элементы) и получим перестановку $$$[5, 1, 2, 4, 3]$$$.
  4. выполним первую операцию (поменяем местами первый и второй элементы) и получим перестановку $$$[1, 5, 2, 4, 3]$$$;

Другой пример — $$$[1, 2, 4, 3]$$$. Минимальную возможную перестановку $$$[1, 2, 3, 4]$$$ можно получить при помощи третьей операции (поменять местами третий и четвертый элементы).

Входные данные

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 100$$$) — количество наборов входных данных. Затем $$$q$$$ следуют наборов входных данных.

Первая строка набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — количество элементов в перестановке.

Вторая строка набора входных данных содержит $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ — заданную перестановку.

Выходные данные

Для каждого набора выходных данных выведите ответ на него — лексикографически минимальную перестановку, полученную путем применения некоторых заданных операций в некотором порядке.

Пример
Входные данные
4
5
5 4 1 3 2
4
1 2 4 3
1
1
4
4 3 2 1
Выходные данные
1 5 2 4 3 
1 2 3 4 
1 
1 4 3 2
Примечание

Напомним, что перестановка $$$p$$$ длины $$$n$$$ лексикографически меньше, чем перестановка $$$q$$$ длины $$$n$$$, если существует такой индекс $$$i \le n$$$, что для всех $$$j$$$ от $$$1$$$ до $$$i - 1$$$ выполняется условие $$$p_j = q_j$$$, а также $$$p_i < q_i$$$. Например:

  • $$$p = [1, 3, 5, 2, 4]$$$ меньше, чем $$$q = [1, 3, 5, 4, 2]$$$ (существует такой индекс $$$i=4$$$, что $$$p_i < q_i$$$, а для всех $$$j < i$$$ выполняется $$$p_j = q_j$$$),
  • $$$p = [1, 2]$$$ меньше, чем $$$q = [2, 1]$$$ (существует такой индекс $$$i=1$$$, что $$$p_i < q_i$$$, а для всех $$$j < i$$$ выполняется $$$p_j = q_j$$$).