#include <iostream>
#include <fstream>
#include <vector>
#define oo 10005
using namespace std;
ifstream f("triangulare.in");
ofstream g("triangulare.out");
int t, n, ind_vector,ramase;
struct p
{
double x, y;
} puncte[55];
class dreapta
{
public:
double x1, y1, x2, y2;
dreapta(double x1, double y1, double x2, double y2)
{
this->x1=x1;
this->y1=y1;
this->x2=x2;
this->y2=y2;
}
dreapta (p a, p b)
{
this->x1=a.x;
this->y1=a.y;
this->x2=b.x;
this->y2=b.y;
}
dreapta()
{
this->x1=this->x2=this->y1=this->y2=0;
}
};
dreapta drepte_existente[70];
vector<pair<int,int>>sol;
p cautare_mijloc(p a, p b)
{
p nou;
nou.x=(a.x+b.x)/2;
nou.y=(a.y+b.y)/2;
return nou;
}
double determinant(dreapta dr, double x, double y)
{
return (dr.x1*dr.y2+dr.x2*y+x*dr.y1-dr.y2*x-dr.y1*dr.x2-dr.x1*y);
}
bool intre_puncte(dreapta a, p b)
{
if (a.y1>a.y2)
{
if (a.y1>=b.y && a.y2<b.y)
return true;
}
if (a.y1<=b.y && a.y2>b.y)
return true;
return false;
}
bool verificare_intersectie(dreapta a, dreapta b)
{
double det1=determinant(a,b.x1,b.y1), det2=determinant(a,b.x2,b.y2), det3=determinant(b,a.x1,a.y1), det4=determinant(b,a.x2,a.y2);
if ((a.x1==b.x1 && a.y1==b.y1) || (a.x1==b.x2 && a.y1==b.y2) || (a.x2==b.x1 && a.y2==b.y1) || (a.x2==b.x2 && a.y2==b.y2))
{
if (det1<0 && det2 >0 && (det3<0 && det4>0 || det3>0 && det4<0) || det2<0 && det1>0 && (det3<0 && det4>0 || det3>0 && det4<0) )
return false;
}
else
{
if (det1<=0 && det2 >=0 && (det3<=0 && det4>=0 || det3>=0 && det4<=0) || det2<=0 && det1>=0 && (det3<=0 && det4>=0 || det3>=0 && det4<=0) )
return false;
}
return true;
}
double determinant2(dreapta dr, p punct)
{
return (dr.x1*dr.y2+dr.x2*punct.y+punct.x*dr.y1-dr.y2*punct.x-dr.y1*dr.x2-dr.x1*punct.y);
}
bool intersectate_paralele(dreapta a, dreapta b)
{
double det1=determinant(a,b.x1,b.y1), det2=determinant(a,b.x2,b.y2), det3=determinant(b,a.x1,a.y1), det4=determinant(b,a.x2,a.y2);
if (det1<0 && det2 >0 && (det3<0 && det4>0 || det3>0 && det4<0) || det2<0 && det1>0 && (det3<0 && det4>0 || det3>0 && det4<0) )
return true;
return false;
}
void cautare_adaugare()
{
for (int i=1; i<=n-2; ++i)
{
for (int j=i+2; j<=n; ++j)
{
if (i==1 && j==n)
break;
dreapta dreapta_incercata(puncte[i],puncte[j]);
p punct_mijloc=cautare_mijloc(puncte[i],puncte[j]);
dreapta paralele_mijloc(punct_mijloc.x,punct_mijloc.y,oo,punct_mijloc.y);
int nr_intersectate=0;
bool posibil=true;
for (int ind_verificare=1; ind_verificare<ind_vector && posibil==true; ++ind_verificare)
{
posibil=verificare_intersectie(dreapta_incercata,drepte_existente[ind_verificare]);
if (posibil==false)
break;
if (ind_verificare<=n && punct_mijloc.y==drepte_existente[ind_verificare].y2 && punct_mijloc.y==drepte_existente[ind_verificare+1].y1)
{
dreapta alta_dr(drepte_existente[ind_verificare].x1,drepte_existente[ind_verificare].y1,drepte_existente[ind_verificare+1].x2,drepte_existente[ind_verificare+1].y2);
if (intersectate_paralele(alta_dr,paralele_mijloc))
nr_intersectate++;
}
if (ind_verificare<=n && intersectate_paralele(drepte_existente[ind_verificare],paralele_mijloc))
{
nr_intersectate++;
}
}
if (posibil==true && nr_intersectate%2==1)
{
dreapta d(puncte[i],puncte[j]);
drepte_existente[ind_vector++]=d;
ramase--;
sol.push_back({i,j});
if (ramase==0)
return;
}
}
}
}
int main()
{
f >> t;
for (int test=0; test<t; ++test)
{
f >> n;
ind_vector=1;
ramase=n-3;
f >> puncte[1].x >> puncte[1].y;
for (int i=2; i<=n; ++i)
{
f >> puncte[i].x >> puncte[i].y;
dreapta d(puncte[i-1].x,puncte[i-1].y,puncte[i].x,puncte[i].y);
drepte_existente[ind_vector++]=d;
}
dreapta d(puncte[n].x,puncte[n].y,puncte[1].x,puncte[1].y);
drepte_existente[ind_vector++]=d;
cautare_adaugare();
for (auto &v:sol)
{
g << v.first-1 <<' ' << v.second-1 << '\n';
}
sol.clear();
}
return 0;
}