Problem: 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).

Input

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

The first line of the test case contains one integer n (1 ≤ n ≤ 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 ≤ 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). 

Solution (in JAVA):

Solution:
import java.io.*;import java.util.Arrays;public class Main { public static void main(String args[]) throws IOException {
      int t=fin();
      while(t-->0){
            int n=fin();
            int a[]=new int[n];
            int b[]=new int[n];
            for(int i=0; i<n; i++)
                  a[i]=fin();
            int x=0;
            while(x<n){
                  int swap=0;
                  for(int i=n-1; i>0; i--){
                        if(b[i]==0)
                              if(a[i-1]>a[i]){
                                    int temp=a[i-1];
                                    a[i-1]=a[i];
                                    a[i]=temp;
                                    b[i]++;
                                    swap++;
                              }
                  }
                  if(swap==0)
                        x=n;
            }
            for(int i=0; i<n; i++)
                  ol(a[i]+" ");
            ol("\n");
      }
      out();
}/*This line contains personally customized codes by Feeham. Also, some code in here is written by different authors. I am thankfull to all of them.*/      static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static void o(String x) throws IOException {bw.write(x+"\n");       }static void o(Integer x) throws IOException {bw.write(x.toString()+"\n");       } static void o(Double x) throws IOException { bw.write(x.toString()+"\n");       } static void o(Double x, int p) throws IOException {  bw.write(String.format("%."+p+"f", x)+"\n");       } static void o(Character x) throws IOException { bw.write(x.toString()+"\n");       }static void ol(String x) throws IOException {bw.write(x); }static void ol(Integer x) throws IOException {bw.write(x.toString());       } static void ol(Double x) throws IOException {bw.write(x.toString());       }static void ol(Double x, int p) throws IOException {  bw.write(String.format("%."+p+"f", x)+"\n");       } static void ol(Character x) throws IOException {bw.write(x.toString());       }static void out(String x) throws IOException {bw.write(x+"\n"); bw.flush();}static void out(Integer x) throws IOException {bw.write(x.toString()+"\n"); bw.flush();      }static void out(Double x) throws IOException {bw.write(x.toString()+"\n"); bw.flush();      }static void out(Double x, int p) throws IOException {  bw.write(String.format("%."+p+"f", x)+"\n"); bw.flush();        } static void out(Character x) throws IOException {bw.write(x.toString()+"\n"); bw.flush();      }static void out() throws IOException {bw.flush();   }static void outl() throws IOException {bw.write("\n");bw.flush();}      static InputReader ir = new InputReader();static int fin(int x)throws IOException {return ir.nextInt();}static long fin(long x)throws IOException {return ir.nextLong();}static int fin()throws IOException {return ir.nextInt();}static Double fin(Double x) throws IOException {return ir.nextDouble();}static char fin(char x) throws IOException{return ir.nextString().charAt(0);}static String fin(String x) throws IOException{return ir.nextLine();}static boolean fin(boolean x) throws IOException{if(ir.nextString().endsWith("rue"))return true;return false;}} /*I am not the owner of this input reader class. All credit and thanks to the owner WilliamFiset*/class InputReader{public static final int DEFAULT_BUFFER_SIZE = 65536, MAX_DECIMAL_PRECISION = 21; public static final InputStream DEFAULT_STREAM; private final byte[] buf; private final InputStream stream;private int c, bufferSize, bufIndex, numBytesRead;private static final byte EOF = -1, NL = 10, SP = 32, DASH = 45, DOT = 46; private static char[] charBuffer; private static byte[] bytes; private static int[] ints; private static char[] chars; private static final double[][] doubles;public InputReader() { this(InputReader.DEFAULT_STREAM, 65536); }  public InputReader(final int n) { this(InputReader.DEFAULT_STREAM, n); } public InputReader(final InputStream inputStream) { this(inputStream, 65536);}public InputReader(final InputStream stream, final int bufferSize) { if (stream == null || bufferSize <= 0) { throw new IllegalArgumentException(); } this.buf = new byte[bufferSize]; this.bufferSize = bufferSize; this.stream = stream;}        private byte read() throws IOException { if (this.numBytesRead == -1) { throw new IOException(); }  if (this.bufIndex >= this.numBytesRead) { this.bufIndex = 0; this.numBytesRead = this.stream.read(this.buf);  if (this.numBytesRead == -1) {  return -1; } } return this.buf[this.bufIndex++]; }private int readJunk(final int n) throws IOException { if (this.numBytesRead == -1) { return -1;  } while (true) {   if (this.bufIndex < this.numBytesRead) { if (this.buf[this.bufIndex] > n) { return 0;  } ++this.bufIndex;  } else { this.numBytesRead = this.stream.read(this.buf); if (this.numBytesRead == -1) {     return -1;    }   this.bufIndex = 0;   }  } }    public byte nextByte() throws IOException {  return (byte)this.nextInt();  }  public int nextInt() throws IOException { if (this.readJunk(44) == -1) { throw new IOException();  } int n = 1; int n2 = 0; this.c = this.buf[this.bufIndex]; if (this.c == 45) { n = -1; ++this.bufIndex; } while (true) { if (this.bufIndex < this.numBytesRead) { if (this.buf[this.bufIndex] <= 32) { ++this.bufIndex;  return n2 * n;  } n2 = (n2 << 3) + (n2 << 1) + InputReader.ints[this.buf[this.bufIndex++]]; } else { this.numBytesRead = this.stream.read(this.buf);  if (this.numBytesRead == -1) { return n2 * n; } this.bufIndex = 0;  } } }public long nextLong() throws IOException { if (this.readJunk(44) == -1) { throw new IOException();  } int n = 1;  long n2 = 0L; this.c = this.buf[this.bufIndex]; if (this.c == 45) { n = -1; ++this.bufIndex;  } while (true) {    if (this.bufIndex < this.numBytesRead) {   if (this.buf[this.bufIndex] <= 32) {   ++this.bufIndex; return n2 * n; } n2 = (n2 << 3) + (n2 << 1) + InputReader.ints[this.buf[this.bufIndex++]]; } else { this.numBytesRead = this.stream.read(this.buf); if (this.numBytesRead == -1) { return n2 * n; } this.bufIndex = 0;  }  } }    private void doubleCharBufferSize() {final char[] charBuffer = new char[InputReader.charBuffer.length << 1];for (int i = 0; i < InputReader.charBuffer.length; ++i) {charBuffer[i] = InputReader.charBuffer[i];}InputReader.charBuffer = charBuffer; }    public String nextLine() throws IOException {  try { this.c = this.read(); } catch (IOException ex) { return null;  } if (this.c == 10) { return ""; } if (this.c == -1) { return null; } int n = 0; InputReader.charBuffer[n++] = (char)this.c; while (true) {  if (this.bufIndex < this.numBytesRead) { if (this.buf[this.bufIndex] == 10) { ++this.bufIndex; return new String(InputReader.charBuffer, 0, n);  } if (n == InputReader.charBuffer.length) { this.doubleCharBufferSize();  } InputReader.charBuffer[n++] = (char)this.buf[this.bufIndex++];  } else { this.numBytesRead = this.stream.read(this.buf); if (this.numBytesRead == -1) {  return new String(InputReader.charBuffer, 0, n); } this.bufIndex = 0; } } }public String nextString() throws IOException {     if (this.numBytesRead == -1) {   return null;     }     if (this.readJunk(32) == -1) {  return null; }   int n = 0; while (true) {   if (this.bufIndex < this.numBytesRead) { if (this.buf[this.bufIndex] <= 32) { ++this.bufIndex; return new String(InputReader.charBuffer, 0, n);  } if (n == InputReader.charBuffer.length) {  this.doubleCharBufferSize();   } InputReader.charBuffer[n++] = (char)this.buf[this.bufIndex++]; }  else { this.numBytesRead = this.stream.read(this.buf); if (this.numBytesRead == -1) { return new String(InputReader.charBuffer, 0, n);   }  this.bufIndex = 0;  }    } }    public double nextDouble() throws IOException { final String nextString = this.nextString();if (nextString == null) { throw new IOException(); } return Double.valueOf(nextString);}    public double nextDoubleFast() throws IOException { this.c = this.read();int n = 1;while (this.c <= 32) {this.c = this.read(); } if (this.c == 45) {n = -1;this.c = this.read(); }double n2 = 0.0;while (this.c > 46) { n2 = n2 * 10.0 + InputReader.ints[this.c];this.c = this.read();} if (this.c == 46) {int n3 = 0; this.c = this.read();while (this.c > 32 && n3 < 21) {n2 += InputReader.doubles[InputReader.ints[this.c]][n3++]; this.c = this.read();}}return n2 * n;}    public byte[] nextByteArray(final int n) throws IOException {final byte[] array = new byte[n];for (int i = 0; i < n; ++i) {array[i] = this.nextByte();     }return array; }    public int[] nextIntArray(final int n) throws IOException {final int[] array = new int[n];for (int i = 0; i < n; ++i) { array[i] = this.nextInt();   } return array;}    public long[] nextLongArray(final int n) throws IOException { final long[] array = new long[n];for (int i = 0; i < n; ++i) {array[i] = this.nextLong();} return array;}    public double[] nextDoubleArray(final int n) throws IOException {final double[] array = new double[n];for (int i = 0; i < n; ++i) { array[i] = this.nextDouble();}return array;}public double[] nextDoubleArrayFast(final int n) throws IOException {final double[] array = new double[n];for (int i = 0; i < n; ++i) {  array[i] = this.nextDoubleFast();}  return array; }    public String[] nextStringArray(final int n) throws IOException {final String[] array = new String[n];for (int i = 0; i < n; ++i) { final String nextString = this.nextString();if (nextString == null) {throw new IOException();}array[i] = nextString; } return array;  }    public byte[] nextByteArray1(final int n) throws IOException {final byte[] array = new byte[n + 1];for (int i = 1; i <= n; ++i) {array[i] = this.nextByte(); }return array;}    public int[] nextIntArray1(final int n) throws IOException {final int[] array = new int[n + 1];for (int i = 1; i <= n; ++i) {    array[i] = this.nextInt();   } return array; }    public long[] nextLongArray1(final int n) throws IOException {final long[] array = new long[n + 1];for (int i = 1; i <= n; ++i) {array[i] = this.nextLong();}return array; }    public double[] nextDoubleArray1(final int n) throws IOException {final double[] array = new double[n + 1];for (int i = 1; i <= n; ++i) {array[i] = this.nextDouble(); }return array;}    public double[] nextDoubleArrayFast1(final int n) throws IOException {final double[] array = new double[n + 1];for (int i = 1; i <= n; ++i) { array[i] = this.nextDoubleFast();  }return array;}public String[] nextStringArray1(final int n) throws IOException {final String[] array = new String[n + 1];for (int i = 1; i <= n; ++i) { array[i] = this.nextString(); }return array;}    public byte[][] nextByteMatrix(final int n, final int n2) throws IOException {final byte[][] array = new byte[n][n2];for (int i = 0; i < n; ++i) {for (int j = 0; j < n2; ++j) { array[i][j] = this.nextByte();} }return array; }    public int[][] nextIntMatrix(final int n, final int n2) throws IOException {final int[][] array = new int[n][n2];for (int i = 0; i < n; ++i) {for (int j = 0; j < n2; ++j) { array[i][j] = this.nextInt();}  }return array;}    public long[][] nextLongMatrix(final int n, final int n2) throws IOException {final long[][] array = new long[n][n2];for (int i = 0; i < n; ++i) {for (int j = 0; j < n2; ++j) {array[i][j] = this.nextLong();}}return array;}    public double[][] nextDoubleMatrix(final int n, final int n2) throws IOException {final double[][] array = new double[n][n2];for (int i = 0; i < n; ++i) { for (int j = 0; j < n2; ++j) {  array[i][j] = this.nextDouble(); } }return array;}    public double[][] nextDoubleMatrixFast(final int n, final int n2) throws IOException {final double[][] array = new double[n][n2]; for (int i = 0; i < n; ++i) {   for (int j = 0; j < n2; ++j) { array[i][j] = this.nextDoubleFast();  } }return array; }    public String[][] nextStringMatrix(final int n, final int n2) throws IOException { final String[][] array = new String[n][n2];for (int i = 0; i < n; ++i) {for (int j = 0; j < n2; ++j) {array[i][j] = this.nextString();}}return array; }    public byte[][] nextByteMatrix1(final int n, final int n2) throws IOException {final byte[][] array = new byte[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) { array[i][j] = this.nextByte(); }}return array;}    public int[][] nextIntMatrix1(final int n, final int n2) throws IOException {final int[][] array = new int[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) {array[i][j] = this.nextInt();}}return array;}    public long[][] nextLongMatrix1(final int n, final int n2) throws IOException {final long[][] array = new long[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) {array[i][j] = this.nextLong();}}return array;}    public double[][] nextDoubleMatrix1(final int n, final int n2) throws IOException { final double[][] array = new double[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) {array[i][j] = this.nextDouble();  } } return array;}    public double[][] nextDoubleMatrixFast1(final int n, final int n2) throws IOException {final double[][] array = new double[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) { array[i][j] = this.nextDoubleFast(); } } return array;}    public String[][] nextStringMatrix1(final int n, final int n2) throws IOException {final String[][] array = new String[n + 1][n2 + 1];for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n2; ++j) {array[i][j] = this.nextString();}}return array;}public void close() throws IOException {this.stream.close();}static { DEFAULT_STREAM = System.in;  InputReader.charBuffer = new char[128]; InputReader.bytes = new byte[58]; InputReader.ints = new int[58]; InputReader.chars = new char[128]; int n = ' '; int n2 = 0; int n3 = 0;  for (int i = 48; i < 58; ++i) {final byte[] bytes = InputReader.bytes;final int n4 = i;final int n5 = n3;n3 = (byte)(n3 + 1);bytes[n4] = (byte)n5;}for (int j = 48; j < 58; ++j) {InputReader.ints[j] = n2++; }for (int k = 32; k < 128; ++k) {final char[] chars = InputReader.chars; final int n6 = k;final int n7 = n;n = (char)(n + '\u0001');chars[n6] = (char)n7;}doubles = new double[][] { { 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 }, { 0.1, 0.01, 0.001, 1.0E-4, 1.0E-5, 1.0E-6, 1.0E-7, 1.0E-8, 1.0E-9, 1.0E-10, 1.0E-11, 1.0E-12, 1.0E-13, 1.0E-14, 1.0E-15, 1.0E-16, 1.0E-17, 1.0E-18, 1.0E-19, 1.0E-20, 1.0E-21 }, { 0.2, 0.02, 0.002, 2.0E-4, 2.0E-5, 2.0E-6, 2.0E-7, 2.0E-8, 2.0E-9, 2.0E-10, 2.0E-11, 2.0E-12, 2.0E-13, 2.0E-14, 2.0E-15, 2.0E-16, 2.0E-17, 2.0E-18, 2.0E-19, 2.0E-20, 2.0E-21 }, { 0.3, 0.03, 0.003, 3.0E-4, 3.0E-5, 3.0E-6, 3.0E-7, 3.0E-8, 3.0E-9, 3.0E-10, 3.0E-11, 3.0E-12, 3.0E-13, 3.0E-14, 3.0E-15, 3.0E-16, 3.0E-17, 3.0E-18, 3.0E-19, 3.0E-20, 3.0E-21 }, { 0.4, 0.04, 0.004, 4.0E-4, 4.0E-5, 4.0E-6, 4.0E-7, 4.0E-8, 4.0E-9, 4.0E-10, 4.0E-11, 4.0E-12, 4.0E-13, 4.0E-14, 4.0E-15, 4.0E-16, 4.0E-17, 4.0E-18, 4.0E-19, 4.0E-20, 4.0E-21 }, { 0.5, 0.05, 0.005, 5.0E-4, 5.0E-5, 5.0E-6, 5.0E-7, 5.0E-8, 5.0E-9, 5.0E-10, 5.0E-11, 5.0E-12, 5.0E-13, 5.0E-14, 5.0E-15, 5.0E-16, 5.0E-17, 5.0E-18, 5.0E-19, 5.0E-20, 5.0E-21 }, { 0.6, 0.06, 0.006, 6.0E-4, 6.0E-5, 6.0E-6, 6.0E-7, 6.0E-8, 6.0E-9, 6.0E-10, 6.0E-11, 6.0E-12, 6.0E-13, 6.0E-14, 6.0E-15, 6.0E-16, 6.0E-17, 6.0E-18, 6.0E-19, 6.0E-20, 6.0E-21 }, { 0.7, 0.07, 0.007, 7.0E-4, 7.0E-5, 7.0E-6, 7.0E-7, 7.0E-8, 7.0E-9, 7.0E-10, 7.0E-11, 7.0E-12, 7.0E-13, 7.0E-14, 7.0E-15, 7.0E-16, 7.0E-17, 7.0E-18, 7.0E-19, 7.0E-20, 7.0E-21 }, { 0.8, 0.08, 0.008, 8.0E-4, 8.0E-5, 8.0E-6, 8.0E-7, 8.0E-8, 8.0E-9, 8.0E-10, 8.0E-11, 8.0E-12, 8.0E-13, 8.0E-14, 8.0E-15, 8.0E-16, 8.0E-17, 8.0E-18, 8.0E-19, 8.0E-20, 8.0E-21 }, { 0.9, 0.09, 0.009, 9.0E-4, 9.0E-5, 9.0E-6, 9.0E-7, 9.0E-8, 9.0E-9, 9.0E-10, 9.0E-11, 9.0E-12, 9.0E-13, 9.0E-14, 9.0E-15, 9.0E-16, 9.0E-17, 9.0E-18, 9.0E-19, 9.0E-20, 9.0E-21 } };}}