#include <bits/stdtr1c++.h>

using namespace std;

int MOD = 1000000007;

struct Matrix {
    int r, c;
    int **mat;

    Matrix(int _r, int _c) {
        r = _r;
        c = _c;
        mat = new int*[r];
        for(int i = 0; i < r; i++) {
            mat[i] = new int[c];
        }
    }

    int get_row() { return r; }
    int get_column() { return c; }

    Matrix multiply(Matrix A) {
        int col = A.get_column();
        Matrix C(r, col);

        for(int i = 0; i < r; i++) {
            for(int j = 0; j < col; j++) {
                C.mat[i][j] = 0;
                for(int k = 0; k < r; k++) {
                    C.mat[i][j] += (mat[i][k] * A.mat[k][j]) % MOD;;
                }
            }
        }
        return C;
    }

    void display() {
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                cout << mat[i][j] << ' ';
            }
            puts("");
        }
    }
};

Matrix F(Matrix A, int n) {
    if(n == 1) return A;
    if(n % 2 == 0) return F(A.multiply(A), n >> 1);
    return A.multiply(F(A.multiply(A), n >> 1));
}

int main() {
    Matrix A(2, 2);
    A.mat[0][0] = 0;
    A.mat[0][1] = 1;
    A.mat[1][0] = 1;
    A.mat[1][1] = 1;
    int a, b, ans, mod, T, t = 1, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d %d %d", &a, &b, &n, &mod);
        Matrix B(2, 1);
        B.mat[0][0] = a;
        B.mat[1][0] = b;
        MOD = (int) pow(10, mod);
        printf("Case %d: ", t++);
        if(n == 0) {
            printf("%d\n", a);
        } else if(n == 1) {
            printf("%d\n", b);
        }else {
            Matrix C = F(A, n);
            ans = C.multiply(B).mat[0][0];
            printf("%d\n", ans);
        }
    }
    return 0;
}