#include <bits/stdc++.h>
using namespace std;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define VI vector<int>
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define endl "\n"
template<class T>inline void read(T &x) {
    x=0; char ch=getchar(); bool f=0;
    for(;ch<'0'||ch>'9';ch=getchar()) f|=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+(ch^48);
    if(f) x=-x;
}
template<class T, class... V>
inline void read(T &a, V&... b){read(a); read(b...);}
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<"="<<x<<endl
#define debugv(x) cerr<<#x<<" : "; ff(i,0,(x).size()) cerr<<(x)[i]<<(i==(x).size()-1?'\n':' ')
#else
#define debug(x)
#define debugv(x)
#endif
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7;
inline ll Pow(ll x,ll y) {
    ll ans = 1;
    for(; y; y >>= 1, x = x * x % mod)
        if(y & 1)
            ans = ans * x % mod;
    return ans;
}
inline ll Add(ll x,ll y) {
    x += y;
    return (x >= mod) ? x - mod : x;
}
inline ll Dec(ll x,ll y) {
    x -= y;
    return (x < 0) ? x + mod : x;
}
inline ll Mul(ll x,ll y) {
    return 1ll * x * y % mod;
}

const int N = 1e6 + 4;
const int value[4] = {0, 1, 3, 2};

string s, t;
int k, r;
int a[N], b[N];
ll f[N];
ll solve(int u, int k) {
    int x = b[u];
    ll tmp = f[u-1] * value[x] % mod;
    if (u == r) {
        return (tmp + (Pow(4, k) + mod - 4) * Pow(3, mod - 2) % mod) % mod;
    }
    return tmp + solve(u-1, k);
}

void Solve() {
    cin >> s >> t >> k;
    int n = s.size(), m = t.size();
    fo(i,1,n) a[n-i+1] ^= s[i-1] - '0';
    fo(i,1,m) a[m-i+1] ^= t[i-1] - '0';
    int len = 0;
    for (;len + 1 <= n || len + 1 <= m; len += 2)
        b[len/2 + 1] = a[len+1] + a[len+2] * 2;
    len = len / 2;
    r = 0;
    while (r < len && b[r+1] == 0) r ++;
    ll ans;
    if (r == len)
        ans =  (Pow(4, k) + mod - 4) * Pow(3, mod - 2) % mod;
    else 
    if (k > r + 1) 
        ans = -1;
    else
        ans = solve(len, k);
    fo(i,1,max(n, m)) a[i] = 0;
    printf("%lld\n", ans);
}
void work() {
    int n = 1e6;
    f[0] = 1;
    fo(i,1,n) f[i] = (f[i-1] * 4 + 1) % mod;
}
int main() {
    work();
    int T = 1;
    //read(T);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> T;
    for(;T--;) Solve();
    return 0;
}