#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("");

    }


}