#include<iostream>
#include<algorithm>
using namespace std;
int n,f[105][10005],T,C,m,i,j,ans;
struct Stone{
int s,e,l;
}stones[105];
bool cmp(Stone a, Stone b){return a.s*b.l<b.s*a.l;}
int main()
{
scanf("%d",&T);
for(C=1;C<=T;C++){
scanf("%d",&n);
m=0;
for(i=1;i<=n;i++){
int s,e,l;
scanf("%d%d%d",&s,&e,&l);
stones[i]={s,e,l},m+=s;
}
sort(stones+1,stones+1+n,cmp);
for(i=1;i<=n;i++)
for(j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=stones[i].s){
int s=stones[i].s,e=stones[i].e,l=stones[i].l;
f[i][j]=max(f[i][j],f[i-1][j-s]+max(0,e-l*(j-s)));
}
}
ans=0;
for(i=0;i<=m;i++)ans=max(ans,f[n][i]);
printf("Case #%d: %d\n",C,ans);
}
return 0;
}