#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = 1e6 + , INF = 0x7fffffff;

int sum1[maxn], sum2[maxn], a[maxn], b[maxn];

int count_(int a, int b)

{

    int cnt = ;

    while(a % b == )

    {

        cnt++;

        a/=b;

    }

    return cnt;

}

int main()

{

    for(int i=; i<maxn; i++)

    {

        a[i] = count_(i, );

        b[i] = count_(i, );

        sum1[i] += sum1[i-] + a[i];

        sum2[i] += sum2[i-] + b[i];

    }

    int n, r, p, q, T, kase = ;

    cin>> T;

    while(T--)

    {

        cin>> n >> r >> p >> q;

        int c = sum1[n] - sum1[r] - sum1[n-r];

        int d = sum2[n] - sum2[r] - sum2[n-r];

        int e = a[p] * q;

        int f = b[p] * q;

        cout<< "Case "<< ++kase <<": " <<min(c+e, d+f) <<endl;

    }

    return ;

}