#include <iostream>
#include <string>
#include <math.h>
using namespace std;
void fun_drukuj(string *tab,int n);
void quicksort(string *tablica, int p, int q);
float odl(string a);
int ile;
int main()
{
cin>>ile; // liczba testow
while(ile--)
{
int n;
cin>>n; // liczba punktow
string *str1;
str1 = new string [n]; //dynamiczna alokacja tablicy
for ( int i=0; i<n; i++)
{
string str;
std::cin.sync();
getline(cin,str); //wczytanie lini
str1[i]=str; //pisanie lini w tablice
}
quicksort(str1,0,n-1); //sortowanie
fun_drukuj(str1,n); // wyświetlanie posortowanych pkt
cout<<endl;
delete [] str1;
}
return 0;
}
void fun_drukuj(string *tab,int n)
{
for(int i=0; i<n; i++)
{
cout << tab[i] << endl;
}
}
void quicksort(string *tablica, int p, int q)
{
string v=tablica[(p+q)/2];
int i,j;
string x;
i=p;
j=q;
do
{
while (odl(tablica[i])<odl(v)) i++; // porównanie odleglosci
while (odl(tablica[j])>odl(v)) j--;
if(i<=j)
{
x=tablica[i];
tablica[i]=tablica[j];
tablica[j]=x;
i++;
j--;
}
}
while(i<=j);
if(j>p) quicksort(tablica,p, j);
if(i<q) quicksort(tablica, i, q);
}
float odl(string a) //funkcja obliczajaca odleglosc
{
int x,y,t;
float s;
x=(int)a[1]-48;
y=(int)a[2]-48;
t=pow(x,2)+pow(y,2);
s=pow(t,0.5);
return s;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8bWF0aC5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgZnVuX2RydWt1aihzdHJpbmcgKnRhYixpbnQgbik7CnZvaWQgcXVpY2tzb3J0KHN0cmluZyAqdGFibGljYSwgaW50IHAsIGludCBxKTsKZmxvYXQgb2RsKHN0cmluZyBhKTsKaW50IGlsZTsKCmludCBtYWluKCkKewogICAgY2luPj5pbGU7ICAgICAgICAgICAgICAgLy8gbGljemJhIHRlc3RvdyAgICAKICAgIHdoaWxlKGlsZS0tKQogICAgewogICAgICAgIGludCBuOwogICAgICAgIGNpbj4+bjsgICAgICAgICAgICAgIC8vIGxpY3piYSBwdW5rdG93CgogICAgICAgIHN0cmluZyAqc3RyMTsKICAgICAgICBzdHIxID0gbmV3IHN0cmluZyBbbl07ICAgICAgICAgIC8vZHluYW1pY3puYSBhbG9rYWNqYSB0YWJsaWN5CgogICAgICAgIGZvciAoIGludCBpPTA7IGk8bjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgc3RyaW5nIHN0cjsKICAgICAgICAgICAgc3RkOjpjaW4uc3luYygpOwogICAgICAgICAgICBnZXRsaW5lKGNpbixzdHIpOyAgICAgICAgICAvL3djenl0YW5pZSBsaW5pIAogICAgICAgICAgICBzdHIxW2ldPXN0cjsgICAgICAgICAgICAgICAvL3Bpc2FuaWUgbGluaSB3IHRhYmxpY2UKCgogICAgICAgIH0KCiAgICAgICAgICBxdWlja3NvcnQoc3RyMSwwLG4tMSk7ICAgICAgIC8vc29ydG93YW5pZQogICAgICAgICAgZnVuX2RydWt1aihzdHIxLG4pOyAgICAgICAgICAgLy8gd3nFm3dpZXRsYW5pZSBwb3NvcnRvd2FueWNoIHBrdAogICAgICAgICAgICBjb3V0PDxlbmRsOwogICAgICAgIGRlbGV0ZSBbXSBzdHIxOwogICAgfQogICAgcmV0dXJuIDA7Cn0KCgp2b2lkIGZ1bl9kcnVrdWooc3RyaW5nICp0YWIsaW50IG4pCnsKCiAgIGZvcihpbnQgaT0wOyBpPG47IGkrKykKICAgIHsKICAgICAgICBjb3V0IDw8IHRhYltpXSA8PCBlbmRsOwogICAgfQp9Cgp2b2lkIHF1aWNrc29ydChzdHJpbmcgKnRhYmxpY2EsIGludCBwLCBpbnQgcSkKewogICAgc3RyaW5nIHY9dGFibGljYVsocCtxKS8yXTsKICAgIGludCBpLGo7CiAgICBzdHJpbmcgeDsKICAgIGk9cDsKICAgIGo9cTsKICAgIGRvCiAgICB7CiAgICAgICAgd2hpbGUgKG9kbCh0YWJsaWNhW2ldKTxvZGwodikpIGkrKzsgICAgICAgLy8gcG9yw7N3bmFuaWUgb2RsZWdsb3NjaQogICAgICAgIHdoaWxlIChvZGwodGFibGljYVtqXSk+b2RsKHYpKSBqLS07CiAgICAgICAgaWYoaTw9aikKICAgICAgICB7CiAgICAgICAgICAgIHg9dGFibGljYVtpXTsKICAgICAgICAgICAgdGFibGljYVtpXT10YWJsaWNhW2pdOwogICAgICAgICAgICB0YWJsaWNhW2pdPXg7CiAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgai0tOwogICAgICAgIH0KICAgIH0KICAgIHdoaWxlKGk8PWopOwogICAgaWYoaj5wKSBxdWlja3NvcnQodGFibGljYSxwLCBqKTsKICAgIGlmKGk8cSkgcXVpY2tzb3J0KHRhYmxpY2EsIGksIHEpOwp9CgpmbG9hdCBvZGwoc3RyaW5nIGEpICAgICAgICAgICAgICAgICAgICAgICAgIC8vZnVua2NqYSBvYmxpY3phamFjYSBvZGxlZ2xvc2MKewogICAgaW50IHgseSx0OwogICAgZmxvYXQgczsKICAgIHg9KGludClhWzFdLTQ4OwogICAgeT0oaW50KWFbMl0tNDg7CiAgICB0PXBvdyh4LDIpK3Bvdyh5LDIpOwogICAgcz1wb3codCwwLjUpOwogICAgcmV0dXJuIHM7Cn0K