Marquito es un niño muy inquieto que gusta de coleccionar programas de todo tipo para su computador. Los programas en su mayoría son juegos para PC debido a la corta edad de marquito y se encuentran almacenados en CD y DVD , dichos programas se encuentran numerados según el orden que los adquirió y llevan el nombre del mismo.

Tiene tantos programas que utiliza un porta discos para guardarlos y acumularlos…el problema surge cuando marquito crece y desarrolla un gusto por ordenar sus cosas y decide empezar con sus programas para lo cual se propone el reto de solo usar dos porta discos adicionales al que tiene.

Su tarea consiste en indicar cuantos cambios debe realizar marquito mientras pasa los discos de uno a otro portadiscos hasta que quede ordenada su colección, tomé en cuenta que los programas no pueden quedar fuera de los 3 porta discos que tiene y marquito puede quedarse con uno en la mano. Al finalizar el programa con más tiempo en su colección debe quedar al inicio de la misma.

La entrada consiste en varios casos de prueba la primera línea indica el número de casos 1<=n<=100, por cada caso de prueba se tiene dos líneas de entrada la primera línea es un numero k entero que indica el número de programas que tiene marquito 1<=k<=10000 la siguiente línea contiene la lista de los k programas que tiene marquito .

La salida consiste en número entero c que indica la cantidad de cambios que debe realizar marquito para ordenar sus programas.