#include <bits/stdtr1c++.h>

using namespace std;

long long MOD = 1000000007;

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

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

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

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

Matrix B(2, 1);

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);
    long long a, b, mod;
    long long mat[2][2] = {{1, 1}, {1, 0}};
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            A.mat[i][j] = mat[i][j];
    int T, t = 1, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld %lld %d %lld", &a, &b, &n, &mod);
        MOD = (int) pow(10, mod);

        B.mat[0][0] = b;
        B.mat[1][0] = a;
        printf("Case %d: \n", t++);
        if(n == 0) {
            printf("%lld\n", a);
        } else if(n == 1) {
            printf("%lld\n", b);
        }else {
            Matrix C = B.multiply(F(A, n - 1));
            for(int i = 0; i < C.get_row(); i++) {
                for(int j = 0; j < C.get_column(); j++) {
                    cout << C.mat[i][j] << ' ';
                }
                puts("");
            }
        }
    }
    return 0;
}