You 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) ((i\ne j)), 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. The first line of input contains a single integer (t) ((1 \leq t \leq 1500)) — the number of test cases. For each test case, the first line contains a single integer (n) ((2 \leq n \leq 3\cdot 10^3)) — the number of cities. Then (n) lines follow, the (i)-th line contains two integers (a_i,b_i) ((0 \leq a_i,b_i \leq 10^9)) — the parameters of city (i). It is guaranteed that the sum of (n^2) over all test cases does not exceed (9\cdot 10^6). For each test case, print (n-1) integers in one line. The (i)-th integer represents the minimum cost when (k=i+1). In the first test case: For (k=2), the optimal path is (1\to 2) with a cost of (\max(0+1,2+2)=4). For (k=3), the optimal path is (2\to 1\to 3) 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 (1\to 4). For (k=3), the optimal path is (2\to 3\to 5). For (k=4), the optimal path is (4\to 1\to 3\to 5). For (k=5), the optimal path is (5\to 2\to 3\to 1\to 4).