/*
Mariusz Redwanz el_paso 6 119436 
HeapSort - sortowanie stogowe
www.algorytm.org
*/

#include<stdio.h>
#include<stdlib.h>
#include<math.h> // funkcja pow
#include<string.h> // funkcja strlen

struct liczba { // struktura przechowujaca dwie postacie wprowadzonej liczby
	char *ulamek; // postac ulamka
	double dziesietnie; // postac dziesietna 
};

/*******************************************************************************************/
void dodaj (int wielkosc, struct liczba tablica[]); // dodawanie kolejnych liczb
void heapsort (int wielkosc, struct liczba tablica[], struct liczba tab_sort[]); // sortowanie przez kopcowanie
void heapify (int wielkosc, struct liczba tablica[], int i); // przywracanie wlasnosci kopca
void build_heap (int wielkosc, struct liczba tablica[]); // budowa kopca
void wyswietl (int wielkosc, struct liczba tablica[]); // wyswietlenie elementow
void usun (int wielkosc, struct liczba tablica[], struct liczba tab_sort[]); // usuwanie elementow stworzonych dynamicznie
/*******************************************************************************************/

int main()
{
    int t, k; // liczba testow i ilosc liczb w tescie
    scanf("%d", &t); 
    while (t--)
    {
          scanf("%d", &k);  
		  struct liczba *tablica = (struct liczba *)malloc((k+1) * sizeof(struct liczba)); // tablica przechowujaca struktury z liczbami
		  struct liczba *tab_sort = (struct liczba *)malloc((k+1) * sizeof(struct liczba)); // posortowane elementy
		  dodaj (k, tablica);
		  build_heap (k, tablica);
		  wyswietl (k, tablica);
		  heapsort (k, tablica, tab_sort);
		  wyswietl (k, tab_sort);
		  printf("\n");
		  usun (k, tablica, tab_sort);
    } 
    return 0;
}
/*******************************************************************************************/
void dodaj (int wielkosc, struct liczba tablica[])
{
	int h, i, j, dlugosc;
	double wynik, liczba1, liczba2; 
	for (h = 1; h <= wielkosc; h++)
	{
		liczba1 = 0; 
        liczba2 = 0;
		char *wejscie = (char *)malloc(16 * sizeof(char)); // wczytywanie ulamka jako ciag znakow 
		scanf("%s", wejscie);
		dlugosc = strlen(wejscie);
		for (i = dlugosc-1, j = 0; wejscie[i] != '/'; i--, j++) // zamiana znakow na liczby
			liczba2 += (wejscie[i]-'0')*pow(10.0, j); 
		for (i--, j = 0; i > 0; i--, j++) 
			liczba1 += (wejscie[i]-'0')*pow(10.0, j);
		if (wejscie[0] == '-') liczba1 *= (-1); // jesli minus przed liczba
		else liczba1 += (wejscie[i]-'0')*pow(10.0, j); // jesli bez minusa
		wynik = liczba1/liczba2; // zapis ulamka w postaci dziesietnej
		struct liczba *nowa = (struct liczba *)malloc(sizeof(struct liczba)); // zapis do struktury 
		tablica[h] = *nowa;
		tablica[h].dziesietnie = wynik;
		tablica[h].ulamek = wejscie;
	}
}
/*******************************************************************************************/
void heapify (int wielkosc, struct liczba tablica[], int i)
{
	int min, left = 2*i, right = 2*i+1;
	if ((left <= wielkosc) && (tablica[left].dziesietnie < tablica[i].dziesietnie)) min = left;
	else min = i;
	if ((right <= wielkosc) && (tablica[right].dziesietnie < tablica[min].dziesietnie)) min = right;
	if (min != i) // nie ma wlasnosci kopca
	{
		tablica[0] = tablica[i];
		tablica[i] = tablica[min];
		tablica[min] = tablica[0];
		heapify (wielkosc, tablica, min);
	}
}
/*********************************************************************************************************/
void build_heap (int wielkosc, struct liczba tablica[])
{
	int i;
	for (i = wielkosc/2; i > 0; i--) 
		heapify (wielkosc, tablica, i);
}
/*********************************************************************************************************/
void heapsort (int wielkosc, struct liczba tablica[], struct liczba tab_sort[])
{
	int i, j;
	for (i = wielkosc, j = 1; i > 1; i--, j++) 
	{
		tab_sort[j] = tablica[1];
		tablica[1] = tablica[i];
		wielkosc--;
		heapify (wielkosc, tablica, 1);
		wyswietl (wielkosc, tablica);
	}
	tab_sort[j] = tablica[1];
}
/*******************************************************************************************/
void wyswietl (int wielkosc, struct liczba tablica[])
{
	int j;
	for (j = 1; j <= wielkosc; j++) 
		printf("%s ", tablica[j].ulamek);
	printf("\n");
}
/*******************************************************************************************/
void usun (int wielkosc, struct liczba tablica[], struct liczba tab_sort[])
{
	free (tablica);
	free (tab_sort);
}
/*******************************************************************************************/