#include<iostream>
#include<sstream>
#include<string>
using namespace std ;
int F(int n , int a , int b){
if(n==0) return a ;
if(n==1) return b ;
int f[n];
f[0] = a ; f[1]=b ;
for(int i = 2 ; i<= n ;i++){
f[i]=f[i-1]+f[i-2] ;
}
return f[n];
}
int main(){
int num_line ;
int a,b,n,m ,t;
stringstream ss ;
string tem , ans ;
cin >> num_line ;
for(int i= 0 ;i<num_line;i++){
cin>>a>>b>>n>>m;
ss << F(n,a,b);
ss >> tem ;
t = tem.size();
if((t-m)<0) m = t;
//本來是寫 if((tem.size()-m)<0) m = tem.size();
//後來多寫了一個t才正確
//檢查的時候發現 cout << tem.size()-2 是一個奇怪的數(很像是輸出一個沒有賦值的數
for(int i = 0 ;i<m ;i++){
if(i == 0&&tem[tem.size()-m+i]=='0') continue;
cout << tem[tem.size()-m+i];
}
ss.clear();
ss.str("");
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHNzdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CmludCBGKGludCBuICwgaW50IGEgLCBpbnQgYil7CiAgICBpZihuPT0wKSByZXR1cm4gYSA7CiAgICBpZihuPT0xKSByZXR1cm4gYiA7CiAgICBpbnQgZltuXTsKICAgIGZbMF0gPSBhIDsgZlsxXT1iIDsKICAgIGZvcihpbnQgaSA9IDIgOyBpPD0gbiA7aSsrKXsKICAgICAgICBmW2ldPWZbaS0xXStmW2ktMl0gOwogICAgfQogICAgcmV0dXJuIGZbbl07Cn0KaW50IG1haW4oKXsKICAgIGludCBudW1fbGluZSA7CiAgICBpbnQgYSxiLG4sbSAsdDsKICAgIHN0cmluZ3N0cmVhbSBzcyA7CiAgICBzdHJpbmcgdGVtICwgYW5zIDsKICAgIGNpbiA+PiBudW1fbGluZSA7CiAgICBmb3IoaW50IGk9IDAgO2k8bnVtX2xpbmU7aSsrKXsKCiAgICAgICAgY2luPj5hPj5iPj5uPj5tOwogICAgICAgIHNzIDw8IEYobixhLGIpOwogICAgICAgIHNzID4+IHRlbSA7CiAgICAgICAgdCA9IHRlbS5zaXplKCk7CiAgICAgICAgaWYoKHQtbSk8MCkgbSA9IHQ7CiAgICAgICAgLy/mnKzkvobmmK/lr6sgaWYoKHRlbS5zaXplKCktbSk8MCkgbSA9IHRlbS5zaXplKCk7CiAgICAgICAgLy/lvozkvoblpJrlr6vkuobkuIDlgIt05omN5q2j56K6CiAgICAgICAgLy/mqqLmn6XnmoTmmYLlgJnnmbznj74gY291dCA8PCB0ZW0uc2l6ZSgpLTIg5piv5LiA5YCL5aWH5oCq55qE5pW477yI5b6I5YOP5piv6Ly45Ye65LiA5YCL5rKS5pyJ6LOm5YC855qE5pW4CiAgICAgICAgZm9yKGludCBpID0gMCA7aTxtIDtpKyspewogICAgICAgICAgICBpZihpID09IDAmJnRlbVt0ZW0uc2l6ZSgpLW0raV09PScwJykgY29udGludWU7CiAgICAgICAgICAgIGNvdXQgPDwgdGVtW3RlbS5zaXplKCktbStpXTsKICAgICAgICB9CiAgICAgICAgc3MuY2xlYXIoKTsKICAgICAgICBzcy5zdHIoIiIpOwoKICAgIH0KCgp9