#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 1000000007
#define sz(x) ((int)((x).size()))
#define int ll
// #define N 
using namespace std;
const int N=1000005;
int f[N],a[N];
void BellaKira()
{
    string x,y;
    cin>>x>>y;
    reverse(x.begin(),x.end());
    reverse(y.begin(),y.end());
    int len=max(sz(x),sz(y));
    for (int i=0;i<len;i++) 
    {
        a[i]=0;
        if (i<sz(x)) a[i]^=(x[i]-'0');
        if (i<sz(y)) a[i]^=(y[i]-'0');
    }
    if (len%2!=0) len++;
    while (len>=2&&a[len-1]==0&&a[len-2]==0) len-=2;
    if (len==0)
    {
        int k;
        cin>>k;
        cout<<f[k-1]<<'\n';
        return;
    }
    int tp=1;
    for (int i=0;i<len;i+=2)
        if (a[i]==0&&a[i+1]==0) tp++;
        else break;
    int k;
    cin>>k;
    // cout<<tp<<" "<<k<<endl;
    if (tp<k)
    {
        cout<<"-1\n";
        return;
    }
    int ans=0;
    for (int i=len-1;i>=0;i-=2)
    {
        if (a[i]==0&&a[i-1]==1) ans=(ans+f[i/2]+1)%mod;
        if (a[i]==1&&a[i-1]==1) ans=(ans+(f[i/2]+1)*2%mod)%mod;
        if (a[i]==1&&a[i-1]==0) ans=(ans+(f[i/2]+1)*3%mod)%mod;
    }
    k--;
    ans=(ans+f[k])%mod;
    cout<<ans<<'\n';
}
signed main()
{
    f[0]=0;
    for (int i=1;i<N;i++) f[i]=(f[i-1]+1)*4;
    IOS;
    cin.tie(0);
    int T=1;
    cin>>T;
    while (T--)
    {
        BellaKira();
    }
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/