#include<bits/stdc++.h>
#define MAX ((int)1e9 + 5)
#define N ((int)1e6 + 5)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;


vector < vector < int > > matMultiply(vector < vector < int > >& matA , vector < vector < int > >& matB, int mod)
{
    int row = matA.size() , col = matB[0].size() , mid = matB.size();
    vector < vector < int > > ans(row , vector < int >(col,0));
    for(int i = 0 ; i < row ; i++){
        for(int j = 0 ; j < col ; j++){
            int val = 0;
            for(int k = 0 ; k < mid ; k++) val = (val + matA[i][k] * matB[k][j]) % mod;
            ans[i][j] = val;
        }
    }
    return ans;
}

vector < vector < int > > bigMod(vector < vector < int > >& mat, int p , int mod)
{
    if(p == 0){
        int row = mat.size();
        vector < vector < int > > ans(row, vector < int >(row,0));
        ans[0][0] = ans[1][1] = 1;
        return ans;
    }
    vector < vector < int > > ans = bigMod(mat , p>>1 , mod);
    ans = matMultiply(ans , ans, mod);
    if(p & 1) ans = matMultiply(ans , mat, mod);
    return ans;
}


int main()
{
    /// problem: https://lightoj.com/problem/number-sequence
    fastio;
    int t , caseNo = 1;
    cin>>t;

    while(t--){
        int a , b , n , m;
        cin>>a>>b>>n>>m;
        vector < vector < int > > mat(2,vector < int >(2,1)) , col(2,vector < int >(1,0));
        col[0][0] = b;
        col[1][0] = a;
        mat[1][1] = 0;
        int mod = 1;
        while(m--) mod *= 10;
        mat = bigMod(mat,n-1,mod);
        vector < vector < int > > ans = matMultiply(mat , col, mod);
        cout<<"Case "<<caseNo++<<": "<<ans[0][0]<<endl;
    }
    return 0;
}