#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll ,ll > PII;
const ll N=1e6+10;
const ll mod=1e9+7;
ll a[N];
ll cnt=0;
ll b[N];
ll bb[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    b[0]=1;
    bb[0]=0;
    for(ll i=1;i<=100;i++){
        b[i]=b[i-1]*4%mod;
        bb[i]=bb[i-1]+b[i];
        bb[i]%=mod;
        // cout<<"bb["<<i<<"]="<<bb[i]<<endl;
    }
    while(t--){
        string s,t;
        cin>>s>>t;
        ll k;
        cin>>k;
        cnt=1;
        ll lens=s.length()-1,lent=t.length()-1;
        if(lens>lent){
            for(ll i=0;i<=lent;i++){
                a[cnt++]=(s[lens-i]-'0')^(t[lent-i]-'0');
            }
            for(ll i=lens-lent-1;i>=0;i--){
                a[cnt++]=(s[i]-'0');
            }
            cnt--;
        }
        else{
            for(ll i=0;i<=lens;i++){
                a[cnt++]=(s[lens-i]-'0')^(t[lent-i]-'0');
            }
            for(ll i=lent-lens-1;i>=0;i--){
                a[cnt++]=(t[i]-'0');
            }
            cnt--;
        }
        // ll f=0;
        while(cnt>=0 && a[cnt]==0) cnt--;
        if(cnt<0){
            cout<<bb[k-1]<<endl;
            continue;
        }
        if(cnt%2==1){
            cnt++;
            a[cnt]=0;
        }
        ll ans=0;
        ll dep=cnt/2-1;
        ans+=bb[dep];
        ll kk=0;
        // cout<<cnt<<endl;
        // for(ll i=1;i<=cnt;i++){
        //     cout<<a[i];
        // }
        // cout<<endl;
        for(ll i=1;i<=cnt;i+=2){
            if(a[i]==0 && a[i+1]==0) kk++;
            else break;
        }
        ll sec=kk+1;
        // cout<<ans<<endl;
        // cout<<kk<<endl;
        while(cnt){
            if(a[cnt]==1 && a[cnt-1]==1){
                ans+=bb[dep]*2+2;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            else if(a[cnt]==0 && a[cnt-1]==1){
                ans+=1;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            else if(a[cnt]==0 && a[cnt-1]==0){
                dep--;
                cnt-=2;
            }
            else{
                ans+=bb[dep]*3+3;
                ans%=mod;
                dep--;
                cnt-=2;
            }
            // cout<<ans<<endl;
        }
        if(k>sec) cout<<-1<<endl;
        else{
            // cout<<ans<<endl;
            ans+=bb[k-1];
            ans%=mod;
            cout<<ans<<endl;
        }
        
    }
    return 0;
}