#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 4;int Mod;int msize;struct Mat{    int mat[N][N];};Mat operator *(Mat a, Mat b){    Mat c;    memset(c.mat, 0, sizeof(c.mat));    for(int k = 0; k < msize; ++k)        for(int i = 0; i < msize; ++i)            if(a.mat[i][k])                for(int j = 0; j < msize; ++j)                    if(b.mat[k][j])                        c.mat[i][j] = ((ll)a.mat[i][k] * b.mat[k][j] + c.mat[i][j])%Mod;    return c;}Mat operator ^(Mat a, int k){    Mat c;    memset(c.mat,0,sizeof(c.mat));    for(int i = 0; i < msize; ++i)        c.mat[i][i]=1;    for(; k; k >>= 1)    {        if(k&1) c = c*a;        a = a*a;    }    return c;}int main(){//    freopen("in.txt", "r", stdin);    int t, a, b, n, m;    msize = 2;    scanf("%d", &t);    while(t--)    {        scanf("%d%d%d%d", &a, &b, &n, &m);        Mod = 1;        while(m--) Mod *= 10;        if(n == 0)        {            printf("%d\n", a%Mod);            continue;        }        Mat A;        A.mat[0][0] = 1, A.mat[0][1] = 1;        A.mat[1][0] = 1, A.mat[1][1] = 0;        A = A^(n-1);        printf("%d\n", (A.mat[0][0]*b + A.mat[0][1]*a)%Mod);    }    return 0;}