#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e6+5;
const ll mod=2315198219;

string s,t;int k;
int xo[N],so[N/2];
ll sk[N];
ll ans;
int tim[4]={0,1,3,2};

void init(int num){
    ll tad=1;
    sk[0]=tad;
    for(int i=1;i<=num;i++){
        tad=tad*4%mod;
        sk[i]=(sk[i-1]+tad)%mod;
    }
}

void solve(){
    ans=0;
    cin>>s>>t>>k;
    reverse(s.begin(),s.end());
    reverse(t.begin(),t.end());
    int n=max(s.size(),t.size());
    for(int i=0;i<n;i++){
        if(i>=s.size())xo[i]=t[i]-'0';
        else if(i>=t.size())xo[i]=s[i]-'0';
        else xo[i]=(s[i]-'0')^(t[i]-'0');
        so[i]=0;
    }
    int m=-1,zr=-1;
    for(int i=0;i<n;i++){
        if(i&1)(so[i>>1]|=(xo[i]<<1));
        else (so[i>>1]|=xo[i]);
        if(so[i>>1]>0){
            m=(i>>1);
            if(zr==-1)zr=(i>>1);
        }
    }
    m++;
    if(m==0){
        cout<<sk[k-1]-sk[0]<<"\n";
        return;
    }
    // cout<<k<<" "<<zr<<"\n";
    if(k>zr+1){
        cout<<-1<<"\n";
        return;
    }
    for(int i=0;i<m;i++){
        ans=(ans+sk[i]*tim[so[i]]%mod)%mod;
    }
    ans=(ans+sk[k-1]-sk[0])%mod;
    cout<<ans<<"\n";
}

int main(){
    // freopen("wait.in","r",stdin);
    // freopen("wait.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    init(1e6);
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
/*
1
 110011001 
1100001111
2
*/
/*
1010010110
*/