CF1256B.Minimize the Permutation

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:

1. perform the second operation (swap the second and the third elements) and obtain the permutation $[5, 1, 4, 3, 2]$;
2. perform the fourth operation (swap the fourth and the fifth elements) and obtain the permutation $[5, 1, 4, 2, 3]$;
3. perform the third operation (swap the third and the fourth elements) and obtain the permutation $[5, 1, 2, 4, 3]$.
4. 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).

给你一个长度为 $n$ 的排列。回忆一下，排列是由 $1$ 到 $n$ 中 $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]$，只需执行第三次操作（交换第三和第四个元素）即可。

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.

输入的第一行包含一个整数 $q$（$1 \le q \le 100$），表示测试用例的数量。随后是 $q$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100$），表示排列中元素的个数。

每个测试用例的第二行包含 $n$ 个互不相同的整数，取值范围为 $1$ 到 $n$，表示给定的排列。

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.

对于每个测试用例，输出其答案——即通过以某种顺序执行给定操作所能得到的字典序最小的排列。

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 \lt 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 \lt q_i$ and for each $j \lt i$ holds $p_j = q_j$),
• $p = [1, 2]$ is less than $q = [2, 1]$ (such $i=1$ exists, that $p_i \lt q_i$ and for each $j \lt i$ holds $p_j = q_j$).

回忆一下，长度为 $n$ 的排列 $p$ 在字典序上小于长度为 $n$ 的排列 $q$，当且仅当存在某个下标 $i \le n$，使得对所有 $j$ 从 $1$ 到 $i - 1$ 均满足 $p_j = q_j$，且 $p_i \lt q_i$。例如：

• $p = [1, 3, 5, 2, 4]$ 小于 $q = [1, 3, 5, 4, 2]$（存在这样的 $i=4$，使得 $p_i \lt q_i$，且对每个 $j \lt i$ 都有 $p_j = q_j$），
• $p = [1, 2]$ 小于 $q = [2, 1]$（存在这样的 $i=1$，使得 $p_i \lt q_i$，且对每个 $j \lt i$ 都有 $p_j = q_j$）。