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;    
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. void choosingDiagonals(vector<vertex>& p, vector<vector<int>>& d, vector<vertex>& uD, int left, int right)
67. {
68.         if (left - right == 1)
69.                 return;
70.  
71.         vertex x;
72.  
73.         x.x = left;
74.         x.y = right;
75.  
76.         uD.push_back(x);
77.  
78.         choosingDiagonals(p, d, uD, left, d[left][right]);
79.         choosingDiagonals(p, d, uD, d[left][right], right);
80. }
81.  
82. long long length(vector<vertex>& uD, vector<vector<long long>>& r)
83. {
84.         long long result = 0;
85.  
86.         for (auto i = uD.begin(); i != uD.end(); i++)
87.                 result += r[(*i).x][(*i).y];
88.  
89.         return result;
90. }
91.  
92. void output(vector<vertex>& uD, long long r)
93. {
94.         cout << r << " ";
95.  
96.         for (auto i = uD.begin(); i != uD.end(); i++)
97.                 cout << (*i).x << " " << (*i).y << " ";
98.  
99.         cout << "\n";
100. }
101.  
102. int main()
103. {
104.         ios_base::sync_with_stdio(0);
105.  
106.         int z;
107.  
108.         cin >> z;
109.  
110.         while (z--)
111.         {
112.                 vector<vertex> polygon;
113.                 vector<vertex> usedDiagonals;
114.                 vector<vector<int>> diagonals;
115.                 vector<vector<long long>> results;
116.                 long long result;
117.  
118.                 input(polygon);
119.                 diagonals.assign(polygon.size(), vector<int>(polygon.size(), -1));
120.                 results.assign(polygon.size(), vector<long long>(polygon.size(), -1));
121.  
122.                 if (polygon.size() > 3)
123.                 {
124.                         findingDiagonals(polygon, diagonals, results, 0, polygon.size() - 1);
125.  
126.                         choosingDiagonals(polygon, diagonals, usedDiagonals, 0, diagonals[0][polygon.size() - 1]);
127.                         choosingDiagonals(polygon, diagonals, usedDiagonals, diagonals[0][polygon.size() - 1], polygon.size() - 1);
128.                 }
129.  
130.                 result = length(usedDiagonals, results);
131.  
132.                 output(usedDiagonals, result);
133.         }
134.  
135.         return 0;
136. }
137.