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