#include<bits/stdc++.h>
#include <cstdio>
using namespace std;
#define ll  long long
#define PB push_back
#define ld long double
#define ff first
#define ss second
# define st(v) (v).begin(),(v).end()
#define   pr pair<int,int>
using namespace std::chrono;
const int N = 1e5+4 , M=N,inf=(int)1e9;
const ll mod=998244353;
int fastAbs(int n) { return (n ^ (n >> 31)) - (n >> 31); }
ll multiply(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) {     return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a%mod) - (b % mod)+ mod) % mod ; }
int ans ;
//map< pair<int,int> , int > mp;
const int dx[4] = {1,0,0,-1};
const int dy[4] = {0,-1,1,0};
bool comp( pair < ll , pair < ll , ll > > x , pair < ll , pair < ll , ll > >  y){
        return (x.ss.ss * y.ff) >= ( y.ss.ss * x.ff );
}
void solve( int x ){
        int n ;
        cin >> n ;
        vector < pair < ll , pair < ll , ll > > > a(n);
        for( int i = 0 ; i < n ; i++){
            cin >> a[i].ff >> a[i].ss.ff >> a[i].ss.ss ;
        }
        sort(st(a),comp);
        const int nmax = 10002 ;
        vector < vector < ll > > dp( n , vector < ll > (nmax,0));
        for( int i = 0 ; i < nmax ; i++){
            if(i >= a[0].ff)
                dp[0][i] = max( (ll)0 , a[0].ss.ff - a[0].ss.ss * (i-a[0].ff) ) ;
        }
        for( int i = 1 ; i < n ; i++){
            for( int j = 0   ; j < nmax ; j++){
                if(j>=a[i].ff){
                    dp[i][j] = max( dp[i-1][j] ,  dp[i-1][j-a[i].ff] + max( (ll)0 , a[i].ss.ff - a[i].ss.ss *(j-a[i].ff))) ;
                }
                else{
                        dp[i][j] = max((ll)0,dp[i-1][j]);
                }
            }
        }
        ll maxm = 0 ;
        for( int i = 0 ; i < nmax ; i++){
            maxm = max( dp[n-1][i], maxm);
        }
        cout << "Case #" << x << ": " << maxm << "\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q=1;
    cin >> q;
    for( int i = 0 ; i < q ; i++){
        solve(i+1);
    }
}
/*
    update - o(1) - log time
*/