1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4.  
5.  
6. using namespace std;
7.  
8. struct vertex
9. {
10.         int x;
11.         int y;
12. };
13.  
14. void input(vector<vertex> p)
15. {
16.         int n;
17.  
18.         cin >> n;
19.  
20.         for (int i = 0; i < n; i++)
21.         {
22.                 vertex v;
23.  
24.                 cin >> v.x >> v.y;
25.  
26.                 p.push_back(v);
27.         }
28. }
29.  
30. long long cost(vertex v, vertex u)
31. {
32.         return ((v.x - u.x)* (v.x - u.x) + (v.y - u.y) * (v.y - u.y));
33. }
34.  
35. long long findingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r,  int left, int right)
36. {
37.         if (r[left][right] != -1)
38.                 return r[left][right];
39.        
40.         if (left - right == -1 || 1)
41.                 return 0;
42.  
43.         long long x = 4000000000000000000;
44.         int v, z;       //z - ile razy ma się wykonać  
45.  
46.         right > left ? z = right - left : z = left - right;
47.  
48.         for (int k = 1; k < z; k++)
49.         {
50.                 long long n;
51.  
52.                 n = cost(p[left], p[k + left]) + cost(p[k + left], p[right - 1]) + findingDiagonals(p, d, r, left, k + left) + findingDiagonals(p, d, r, k + left, right);
53.  
54.                 if (n < x)
55.                 {
56.                         x = n;
57.                         v = k;
58.                 }
59.         }
60.  
61.         d[left][right] = v;
62.         r[left][right] = x;
63.  
64.         return x;
65. }
66.  
67. vertex choosingFirstDiagonal(vector<vertex>& p, vector<vector<int>>& d, vector<vector<long long>>& r)
68. {
69.         long long x = 4000000000000000000;
70.         int minI, minJ;
71.  
72.         for(int i = 0; i < p.size() - 1; i++)
73.                 for (int j = 1; j < p.size(); j++)
74.                 {
75.                         long long n;
76.  
77.                         n = cost(p[i], p[j]) + findingDiagonals(p, d, r, i, j) + findingDiagonals(p, d, r, j, i);
78.  
79.                         if (n < x)
80.                         {
81.                                 x = n;
82.                                 minI = i;
83.                                 minJ = j;
84.                         }
85.                 }
86.  
87.         vertex v;
88.         v.x = minI;
89.         v.y = minJ;
90.  
91.         return v;
92. }
93.  
94. void choosingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vertex>& uD, vertex fD)
95. {
96.         if (fD.x - fD.y == -1 || 1)
97.                 return;
98.  
99.         uD.push_back(fD);
100.  
101.         vertex u, v;
102.  
103.         u = v = fD;
104.  
105.         u.x = d[fD.x][fD.y];
106.         v.y = d[fD.x][fD.y];
107.  
108.         choosingDiagonals(p, d, uD, u);
109.         choosingDiagonals(p, d, uD, v);
110. }
111.  
112. long long length(vector<vertex>& uD, vector<vector<long long>>& r)
113. {
114.         long long result = 0;
115.  
116.         for (auto i = uD.begin(); i != uD.end(); i++)
117.                 result += r[(*i).x][(*i).y];
118.  
119.         return result;
120. }
121.  
122. void output(vector<vertex>& uD, long long r)
123. {
124.         cout << r << " ";
125.  
126.         for (auto i = uD.begin(); i != uD.end(); i++)
127.                 cout << (*i).x << " " << (*i).y << " ";
128.  
129.         cout << "\n";
130. }
131.  
132. int main()
133. {
134.         ios_base::sync_with_stdio(0);
135.  
136.         int z;
137.  
138.         cin >> z;
139.  
140.         while (z--)
141.         {
142.                 vector<vertex> polygon;
143.                 vector<vertex> usedDiagonals;
144.                 vector<vector<int>> diagonals;
145.                 vector<vector<long long>> results;
146.                 long long result;
147.  
148.                 input(polygon);
149.                 diagonals.assign(polygon.size() + 1, vector<int>(polygon.size() + 1, -1));
150.                 results.assign(polygon.size() + 1, vector<long long>(polygon.size() + 1, -1));
151.  
152.                 vertex fDiag = choosingFirstDiagonal(polygon, diagonals, results);
153.  
154.                 choosingDiagonals(polygon, diagonals, usedDiagonals, fDiag);
155.  
156.                 result = length(usedDiagonals, results);
157.  
158.                 output(usedDiagonals, result);
159.         }
160.  
161.         return 0;
162. }