#include <bits/stdc++.h>

#define loli unsigned long long
#define eps 1e-8
#define fastIO ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define endl '\n'
#define mod 1000000007
#define N 3000


using namespace std;

loli n,s1,v1,s2,v2;
int time0=0;

inline loli gcd(loli a,loli b)
{
    while(b!=0){
        a%=b;
        swap(a,b);
    }

    return a;
}

inline void init()
{
    scanf("%llu%llu%llu%llu%llu", &n, &s1, &v1, &s2, &v2);
}

inline void solve()
{
    loli ans=0,GCD=gcd(s1,s2);
    loli mul=s1/GCD*s2;
    ans+=(n/mul*max(mul/s1*v1,mul/s2*v2));

    n%=mul;

    if(s1>s2){
        loli tmp=0,tmp2;
        for(loli i=0;i<=n/s1;++i){
            tmp2= (i*v1)+floor((n-i*s1)/(long double)s2)*v2;
            if(tmp<tmp2)
                tmp=tmp2;
        }
        ans+=tmp;
    }
    else{
        loli tmp=0,tmp2;
        for(loli i=0;i<=n/s2;++i){
            tmp2= (i*v2)+floor((n-i*s2)/(long double)s1)*v1;
            if(tmp<tmp2)
                tmp=tmp2;
        }
        ans+=tmp;
    }

    printf("Case #%d: %llu\n", ++time0, ans);
}

int main()
{
    //fastIO;

    int t;
    scanf("%d",&t);
    while(t--){
        init();
        solve();
    }

    return 0;
}