读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：minimize.in

输出：minimize.out

题目描述

给你一个长度为 $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$ —— 给定的排列。

输出格式

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

输入输出样例

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

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

说明/提示

回想一下，对于长度为 $n$ 的排列 $p$ 和 $q$，如果存在一个索引 $i \le n$，使得对于所有从 $1$ 到 $i-1$ 的 $j$ 满足条件 $p_j = q_j$，且 $p_i < q_i$，则称排列 $p$ 的字典序小于排列 $q$。例如：

• $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$）