#include <bits/stdc++.h>
typedef long long int var;
const int NMAX  = 505;
using namespace std;

ifstream fin("calatorie.in");
ofstream fout("calatorie.out");


struct Hash{

int n,h;

}V[55];

bitset < NMAX > B[55],b[55];
var D[NMAX],d[NMAX];

void calatorie(int s, int n, var S){

    var Smx = 1e10;
    for(int i = 1; i < n; i++){
        for(int j = s; j >= 0; j--){
            D[j + V[i].h] = max(D[j] + V[i].n , D[j + V[i].h]);

        }
    }
    for(int i = 1; i <= s; i++){
            Smx = min(Smx , (S - D[i]) + 1LL * i * i * i * i);
        fout << D[i] << " ";
        }
    for(int i = 1; i <= s + 10; i ++){
        B[i] =  0;
        D[i] = 0;
    }

    fout << "Consumul minim = " << Smx << "." << "\n";

}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);
    var n,T,S;

    fin >> T;

    for(int k = 1; k <= T; k++){
        fin >> n;
        S = 0;
        for(int i = 1 ; i < n; i++){
            fin >> V[i].n >> V[i].h;
            S += V[i].n;
        }
        calatorie(sqrt(sqrt(S)), n, S);

    }

    return 0;
}