package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

const INF int64 = 1e18

type City struct {
	a int64
	b int64
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var n int
		fmt.Fscan(reader, &n)

		cities := make([]City, n+1)
		for i := 1; i <= n; i++ {
			fmt.Fscan(reader, &cities[i].a, &cities[i].b)
		}

		sort.Slice(cities[1:], func(i, j int) bool {
			return (cities[1+i].a - cities[1+i].b) < (cities[1+j].a - cities[1+j].b)
		})

		dpL := make([][][3]int64, n+2)
		dpR := make([][][3]int64, n+2)
		for i := 0; i <= n+1; i++ {
			dpL[i] = make([][3]int64, n/2+2)
			dpR[i] = make([][3]int64, n/2+2)
			for k := 0; k <= n/2+1; k++ {
				for e := 0; e < 3; e++ {
					dpL[i][k][e] = INF
					dpR[i][k][e] = INF
				}
			}
		}

		dpL[0][0][0] = 0
		for i := 1; i <= n; i++ {
			for k := 0; k <= n/2+1; k++ {
				for e := 0; e < 3; e++ {
					dpL[i][k][e] = dpL[i-1][k][e]
					if k > 0 {
						if dpL[i-1][k-1][e] != INF {
							dpL[i][k][e] = min(dpL[i][k][e], dpL[i-1][k-1][e]+2*cities[i].b)
						}
						if e > 0 && dpL[i-1][k-1][e-1] != INF {
							dpL[i][k][e] = min(dpL[i][k][e], dpL[i-1][k-1][e-1]+cities[i].b)
						}
					}
				}
			}
		}

		dpR[n+1][0][0] = 0
		for i := n; i >= 1; i-- {
			for k := 0; k <= n/2+1; k++ {
				for e := 0; e < 3; e++ {
					dpR[i][k][e] = dpR[i+1][k][e]
					if k > 0 {
						if dpR[i+1][k-1][e] != INF {
							dpR[i][k][e] = min(dpR[i][k][e], dpR[i+1][k-1][e]+2*cities[i].a)
						}
						if e > 0 && dpR[i+1][k-1][e-1] != INF {
							dpR[i][k][e] = min(dpR[i][k][e], dpR[i+1][k-1][e-1]+cities[i].a)
						}
					}
				}
			}
		}

		for c := 2; c <= n; c++ {
			ans := INF
			k := c / 2
			if c%2 == 0 {
				for i := 0; i <= n; i++ {
					val := dpL[i][k][1] + dpR[i+1][k][1]
					if val < ans {
						ans = val
					}
				}
			} else {
				for i := 0; i <= n; i++ {
					val1 := dpL[i][k][0] + dpR[i+1][k+1][2]
					if val1 < ans {
						ans = val1
					}

					val2 := dpL[i][k+1][2] + dpR[i+1][k][0]
					if val2 < ans {
						ans = val2
					}
				}
				for i := 1; i <= n; i++ {
					val3 := dpL[i-1][k][1] + cities[i].a + cities[i].b + dpR[i+1][k][1]
					if val3 < ans {
						ans = val3
					}
				}
			}
			if c == n {
				fmt.Fprintf(writer, "%d\n", ans)
			} else {
				fmt.Fprintf(writer, "%d ", ans)
			}
		}
	}
}