#include <bits/stdc++.h>

typedef unsigned long long var;
const var NMAX = 55;
const var MMAX = 505;

using namespace std;

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

var D[NMAX][MMAX],Dh[NMAX][MMAX],N[NMAX],H[NMAX];

var Pow(var x){
    return x * x * x * x;
}

int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int T,n,mh;
    var sol;
    fin >> T;
    for(int k = 1; k <= T; k++){

        fin >> n;
        n--; mh = 0;
        for(int i = 1; i <= n; i++)
            fin >> N[i] >> H[i],mh += H[i];

        for(int i  = 1; i <= n; i++){
            for(int j = mh; j >= H[i]; j--){
                if(D[i - 1][j] + N[i] + Pow(D[i - 1][j]) <= D[i - 1][j - H[i]] + Pow(Dh[i][j - H[i]] + H[i])){
                    Dh[i][j] = Dh[i - 1][j];
                    D[i][j] =  D[i - 1][j] + N[i];
                }

                else{
                    D[i][j] = D[i - 1][j - H[i]];s
                    Dh[i][j] = Dh[i - 1][j - H[i]] + H[i];
                }
            }
            for(int j = 1; j < H[i]; j++){
                Dh[i][j] = Dh[i - 1][j];
                D[i][j] =  D[i - 1][j] + N[i];
            }

        }
        sol = 1e15;
        for(int i  = 1; i <= mh; i++)
            sol = min(sol,D[n][i] + Pow(Dh[n][i]));

        fout << sol << "\n";
    }
    return 0;
}