#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
*/
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGNzdGRpbz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCAgbG9uZyBsb25nCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgbGQgbG9uZyBkb3VibGUKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojIGRlZmluZSBzdCh2KSAodikuYmVnaW4oKSwodikuZW5kKCkKI2RlZmluZSAgIHByIHBhaXI8aW50LGludD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDo6Y2hyb25vOwpjb25zdCBpbnQgTiA9IDFlNSs0ICwgTT1OLGluZj0oaW50KTFlOTsKY29uc3QgbGwgbW9kPTk5ODI0NDM1MzsKaW50IGZhc3RBYnMoaW50IG4pIHsgcmV0dXJuIChuIF4gKG4gPj4gMzEpKSAtIChuID4+IDMxKTsgfQpsbCBtdWx0aXBseShsbCBhLCBsbCBiKXsgcmV0dXJuICgoYSAlIG1vZCkgKiAoYiAlIG1vZCkpICUgbW9kOyB9CmxsIGFkZChsbCBhLCBsbCBiKSB7ICAgICByZXR1cm4gKChhICUgbW9kKSArIChiICUgbW9kKSkgJSBtb2Q7IH0KbGwgc3ViKGxsIGEsIGxsIGIpIHsgcmV0dXJuICgoYSVtb2QpIC0gKGIgJSBtb2QpKyBtb2QpICUgbW9kIDsgfQppbnQgYW5zIDsKLy9tYXA8IHBhaXI8aW50LGludD4gLCBpbnQgPiBtcDsKY29uc3QgaW50IGR4WzRdID0gezEsMCwwLC0xfTsKY29uc3QgaW50IGR5WzRdID0gezAsLTEsMSwwfTsKYm9vbCBjb21wKCBwYWlyIDwgbGwgLCBwYWlyIDwgbGwgLCBsbCA+ID4geCAsIHBhaXIgPCBsbCAsIHBhaXIgPCBsbCAsIGxsID4gPiAgeSl7CiAgICAgICAgcmV0dXJuICh4LnNzLnNzICogeS5mZikgPj0gKCB5LnNzLnNzICogeC5mZiApOwp9CnZvaWQgc29sdmUoIGludCB4ICl7CiAgICAgICAgaW50IG4gOwogICAgICAgIGNpbiA+PiBuIDsKICAgICAgICB2ZWN0b3IgPCBwYWlyIDwgbGwgLCBwYWlyIDwgbGwgLCBsbCA+ID4gPiBhKG4pOwogICAgICAgIGZvciggaW50IGkgPSAwIDsgaSA8IG4gOyBpKyspewogICAgICAgICAgICBjaW4gPj4gYVtpXS5mZiA+PiBhW2ldLnNzLmZmID4+IGFbaV0uc3Muc3MgOwogICAgICAgIH0KICAgICAgICBzb3J0KHN0KGEpLGNvbXApOwogICAgICAgIGNvbnN0IGludCBubWF4ID0gMTAwMDIgOwogICAgICAgIHZlY3RvciA8IHZlY3RvciA8IGxsID4gPiBkcCggbiAsIHZlY3RvciA8IGxsID4gKG5tYXgsMCkpOwogICAgICAgIGZvciggaW50IGkgPSAwIDsgaSA8IG5tYXggOyBpKyspewogICAgICAgICAgICBpZihpID49IGFbMF0uZmYpCiAgICAgICAgICAgICAgICBkcFswXVtpXSA9IG1heCggKGxsKTAgLCBhWzBdLnNzLmZmIC0gYVswXS5zcy5zcyAqIChpLWFbMF0uZmYpICkgOwogICAgICAgIH0KICAgICAgICBmb3IoIGludCBpID0gMSA7IGkgPCBuIDsgaSsrKXsKICAgICAgICAgICAgZm9yKCBpbnQgaiA9IDAgICA7IGogPCBubWF4IDsgaisrKXsKICAgICAgICAgICAgICAgIGlmKGo+PWFbaV0uZmYpewogICAgICAgICAgICAgICAgICAgIGRwW2ldW2pdID0gbWF4KCBkcFtpLTFdW2pdICwgIGRwW2ktMV1bai1hW2ldLmZmXSArIG1heCggKGxsKTAgLCBhW2ldLnNzLmZmIC0gYVtpXS5zcy5zcyAqKGotYVtpXS5mZikpKSA7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IG1heCgobGwpMCxkcFtpLTFdW2pdKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBsbCBtYXhtID0gMCA7CiAgICAgICAgZm9yKCBpbnQgaSA9IDAgOyBpIDwgbm1heCA7IGkrKyl7CiAgICAgICAgICAgIG1heG0gPSBtYXgoIGRwW24tMV1baV0sIG1heG0pOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8ICJDYXNlICMiIDw8IHggPDwgIjogIiA8PCBtYXhtIDw8ICJcbiI7Cn0KaW50IG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKICAgIGludCBxPTE7CiAgICBjaW4gPj4gcTsKICAgIGZvciggaW50IGkgPSAwIDsgaSA8IHEgOyBpKyspewogICAgICAgIHNvbHZlKGkrMSk7CiAgICB9Cn0KLyoKICAgIHVwZGF0ZSAtIG8oMSkgLSBsb2cgdGltZQoqLwo=