Hoán vị nhỏ nhất theo thứ tự từ điển

Cho một hoán vị $p$ gồm $n$ phần tử, tức là một dãy chứa đúng một lần mỗi số nguyên từ $1$ đến $n$.

Bạn được phép thực hiện $n-1$ thao tác. Thao tác thứ $i$ (với $1\le i\le n-1$) đổi chỗ hai phần tử đang đứng ở vị trí $i$ và vị trí $i+1$ của hoán vị hiện tại.

Mỗi thao tác chỉ được dùng nhiều nhất một lần, nhưng bạn có thể chọn thực hiện chúng theo thứ tự tuỳ ý, và cũng có thể bỏ qua thao tác nào tuỳ thích (kể cả không thực hiện thao tác nào).

Hãy tìm hoán vị nhỏ nhất theo thứ tự từ điển có thể thu được.

Hoán vị $p$ nhỏ hơn hoán vị $q$ (cùng độ dài $n$) theo thứ tự từ điển nếu tồn tại chỉ số $i$ sao cho $p_j=q_j$ với mọi $j<i$ và $p_i<q_i$.

Bạn phải trả lời $q$ bộ dữ liệu độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $n$ là độ dài hoán vị.
  • Dòng thứ hai chứa $n$ số nguyên đôi một khác nhau từ $1$ đến $n$ mô tả hoán vị.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng $n$ số nguyên là hoán vị nhỏ nhất theo thứ tự từ điển thu được.

Ràng buộc

• $1\le q\le 100$
• $1\le n\le 100$
• Dãy đã cho luôn là một hoán vị của $1,2,\dots ,n$.

Ví dụ