using System;
using System.Text;

namespace ZigZag
{
    class Program
    {
        static void Main(String[] args)
        {
            int t = Int32.Parse(Console.ReadLine());
            for(int i = 0; i < t; i++)
            {
                int n= Int32.Parse(Console.ReadLine());
                int[] array = Array.ConvertAll(Console.ReadLine().Split(' '),Int32.Parse);
                int rel = 0; //0->greater than , 1->less than
                for(int j = 1; j < n; j++)
                {

                    Console.WriteLine(rel + " " + j);
                    if (rel == 0) {
                        rel = 1;
                        if (array[j] <= array[j - 1]) swap(array, j - 1, j);
                    }
                    else
                    {
                        rel = 0;
                        if (array[j - 1] <= array[j]) swap(array, j - 1, j);
                    }
                }
                for (int j = 0; j < n; j++) Console.Write(array[j]+" ");
                Console.WriteLine();
            }    
        }
        private static void swap(int[] array, int a, int b)
        {
            int temp = array[a];
            array[a] = array[b];
            array[b] = temp;
        }
    }
}
