puts gets.to_i.times.map{
	klr = gets.to_i.times.map{ gets.split.map(&:to_i) }
	嬉,ls,rs = 0,[0],[0]
	klr.sort_by{|_,l,r| (l-r).abs }.reverse_each{|lk,l,r|
		if l==r
			嬉 += l
		else
			k,s,hi,lo = l<r ? [klr.size-lk,rs,r,l] : [lk,ls,l,r]
			if s.size <= k || k < s[k]
				嬉 += hi
				s.insert(s.bsearch_index{|_|k<_}||s.size,k)
			else
				嬉 += lo
			end
		end
	}
	next 嬉
}
