write a go solution for F. Traveling Salescattime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are a cat selling fun algorithm problems. Today, you want to recommend your fun algorithm problems to k cities.There are a total of n cities, each with two parameters a_i and b_i. Between any two cities i,j (inej), there is a bidirectional road with a length of max(a_i+b_j,b_i+a_j). The cost of a path is defined as the total length of roads between every two adjacent cities along the path.For k=2,3,ldots,n, find the minimum cost among all simple paths containing exactly k distinct cities.InputThe first line of input contains a single integer t (1<=t<=1500) — the number of test cases.For each test case, the first line contains a single integer n (2<=qn<=q3*10^3) — the number of cities.Then n lines follow, the i-th line contains two integers a_i,b_i (0<=a_i,b_i<=10^9) — the parameters of city i.It is guaranteed that the sum of n^2 over all test cases does not exceed 9*10^6.OutputFor each test case, print n-1 integers in one line. The i-th integer represents the minimum cost when k=i+1.ExampleInput330 22 13 352 77 56 31 87 58899167687 609615846851467150 45726720931502759 23784096918190644 196992738142090421 475722765409556751 726971942513558832 998277529294328304 434714258Output4 9 
10 22 34 46 
770051069 1655330585 2931719265 3918741472 5033924854 6425541981 7934325514 
NoteIn the first test case: For k=2, the optimal path is 1to2 with a cost of max(0+1,2+2)=4. For k=3, the optimal path is 2to1to3 with a cost of max(0+1,2+2)+max(0+3,3+2)=4+5=9. In the second test case: For k=2, the optimal path is 1to4. For k=3, the optimal path is 2to3to5. For k=4, the optimal path is 4to1to3to5. For k=5, the optimal path is 5to2to3to1to4.. Output only the code with no comments, explanation, or additional text.