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 || 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 || 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.         vertex v;
87.         v.x = minI;
88.         v.y = minJ;
89.  
90.         return v;
91. }
92.  
93. void choosingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vertex>& uD, vertex fD)
94. {
95.         if (fD.x - fD.y == -1 || fD.x - fD.y == 1)
96.                 return;
97.  
98.         uD.push_back(fD);
99.  
100.         vertex u, v;
101.  
102.         u = v = fD;
103.  
104.         u.x = d[fD.x][fD.y];
105.         v.y = d[fD.x][fD.y];
106.  
107.         choosingDiagonals(p, d, uD, u);
108.         choosingDiagonals(p, d, uD, v);
109. }
110.  
111. long long length(vector<vertex>& uD, vector<vector<long long>>& r)
112. {
113.         long long result = 0;
114.  
115.         for (auto i = uD.begin(); i != uD.end(); i++)
116.                 result += r[(*i).x][(*i).y];
117.  
118.         return result;
119. }
120.  
121. void output(vector<vertex>& uD, long long r)
122. {
123.         cout << r << " ";
124.  
125.         for (auto i = uD.begin(); i != uD.end(); i++)
126.                 cout << (*i).x << " " << (*i).y << " ";
127.  
128.         cout << "\n";
129. }
130.  
131. int main()
132. {
133.         ios_base::sync_with_stdio(0);
134.  
135.         int z;
136.  
137.         cin >> z;
138.  
139.         while (z--)
140.         {
141.                 vector<vertex> polygon;
142.                 vector<vertex> usedDiagonals;
143.                 vector<vector<int>> diagonals;
144.                 vector<vector<long long>> results;
145.                 long long result;
146.  
147.                 input(polygon);
148.                 diagonals.assign(polygon.size() + 1, vector<int>(polygon.size() + 1, -1));
149.                 results.assign(polygon.size() + 1, vector<long long>(polygon.size() + 1, -1));
150.  
151.                 vertex fDiag = choosingFirstDiagonal(polygon, diagonals, results);
152.  
153.                 choosingDiagonals(polygon, diagonals, usedDiagonals, fDiag);
154.  
155.                 for(auto i = results.begin(); i != results.end(); i++)
156.  
157.  
158.                 result = length(usedDiagonals, results);
159.  
160.                 output(usedDiagonals, result);
161.         }
162.  
163.         return 0;
164. }
165.