#include <bits/stdc++.h>
using namespace std;

const int N = 110, M = N  * N;

struct Stone{
    int s, e, l;
}stone[N];

int f[N][M];

int T, n, m;

bool cmp(Stone s1, Stone s2)
{
    return s1.s * s2.l < s2.s * s1.l;
}

int main()
{
    cin >> T;

    for(int k = 1; k <= T; k++)
    {
        memset(f,0,sizeof 0);
        cin >> n;
        m = 0;
        for(int i = 1; i <= n; i++) 
        {
            cin >> stone[i].s >> stone[i].e >> stone[i].l;
            m += stone[i].s;
        }
        sort(stone+1,stone+1+n,cmp);

        for(int i = 1; i <= n; i++)
        {
            int s = stone[i].s, e = stone[i].e, l = stone[i].l;

            for(int j = 0; j <= m; j++)
            {
                f[i][j] = f[i-1][j];

                if(j >= s)
                f[i][j] = max(f[i][j],f[i-1][j-s]+e-l*(j-s));
            }
        }

        int res = -1;
        for(int j = 0; j <= m; j++) res = max(res,f[n][j]);

        printf("Case #%d: %d\n",k,res);
    }

    return 0;
}