#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

struct vertex
{
	int x;
	int y;
};

void input(vector<vertex>& p)
{
	int n;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		vertex v;

		cin >> v.x >> v.y;

		p.push_back(v);
	}
}

long long cost(vertex v, vertex u, int diff)
{
	if (diff == 1) return 0;
	return ((v.x - u.x) * (v.x - u.x) + (v.y - u.y) * (v.y - u.y));
}

long long findingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r, int left, int right)
{
	if (r[left][right] != -1)
		return r[left][right];

	if (left - right == 1)
		return 0;

	long long x = 4000000000000000000;
	int v = -1;	//z - ile razy ma się wykonać  

	for (int k = left + 1; k < right; k++)
	{
		long long n;

		n = cost(p[left], p[k], left - right) + cost(p[k + 1], p[right], left - right) + findingDiagonals(p, d, r, left, k) + findingDiagonals(p, d, r, k + 1, right);

		if (n < x)
		{
			x = n;
			v = k;
		}
	}

	d[left][right] = v;
	r[left][right] = x;

	return x;
}

vertex choosingFirstDiagonal(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r)
{
	long long x = 4000000000000000000;
	int minI, minJ;

	for (int i = 0; i < p.size() - 1; i++)
		for (int j = i + 1; j < p.size(); j++)
		{
			long long n;

			n = cost(p[i], p[j], j - i) + findingDiagonals(p, d, r, i, j);

			if (n < x)
			{
				x = n;
				minI = i;
				minJ = j;
			}
		}

	

	vertex v;
	v.x = minI;
	v.y = minJ;

	return v;
}

void choosingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vertex>& uD, vertex fD)
{
	if (fD.x - fD.y == 1)
		return;

	uD.push_back(fD);

	vertex u, v;

	u = v = fD;

	u.x = d[fD.x][fD.y];
	v.y = d[fD.x][fD.y];

	choosingDiagonals(p, d, uD, u);
	choosingDiagonals(p, d, uD, v);
}

long long length(vector<vertex>& uD, vector<vector<long long>>& r)
{
	long long result = 0;

	for (auto i = uD.begin(); i != uD.end(); i++)
		result += r[(*i).x][(*i).y];

	return result;
}

void output(vector<vertex>& uD, long long r)
{
	cout << r << " ";

	for (auto i = uD.begin(); i != uD.end(); i++)
		cout << (*i).x << " " << (*i).y << " ";

	cout << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);

	int z;

	cin >> z;

	while (z--)
	{
		vector<vertex> polygon;
		vector<vertex> usedDiagonals;
		vector<vector<int>> diagonals;
		vector<vector<long long>> results;
		long long result;

		input(polygon);
		diagonals.assign(polygon.size() + 1, vector<int>(polygon.size() + 1, -1));
		results.assign(polygon.size() + 1, vector<long long>(polygon.size() + 1, -1));\

		if (polygon.size() > 3)
		{
			vertex fDiag = choosingFirstDiagonal(polygon, diagonals, results);

			choosingDiagonals(polygon, diagonals, usedDiagonals, fDiag);
		}

		result = length(usedDiagonals, results);

		output(usedDiagonals, result);
	}

	return 0;
}