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

#define F first
#define S second 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;

const int N = 1e6 + 2;

set<int> g[N];

const int K = 10;
int sz = 0;
int need = (1 << 8);

const int mod = 1e9 + 7;

void dfs(int v) {
    if (v == need) cout << sz << '\n';
    sz++;
    //cout << (k++) << ": " << (bitset<K>(v)) << '\n';
    if (g[v].size()) {
        int i = *g[v].begin();
        g[v].erase(i);
        g[v^(1<<i)].erase(i);
        dfs(v ^ (1<<i));
    }
}

void solve() {
    map<string, long long> val;
    val["00"] = 0;
    val["10"] = 1;
    val["11"] = 2;
    val["01"] = 3;
    string s, t;
    int k;
    cin >> s >> t >> k;
    reverse(all(s));
    reverse(all(t));
    while (sz(s) < max(sz(s), sz(t))) s += "0";
    while (sz(t) < max(sz(s), sz(t))) t += "0";
    for (int i = 0; i < sz(s); ++i) {
        if (s[i] == '1') t[i] ^= 1;
    }
    if (sz(t) & 1) t += "0";
    long long pos = 0, pw = 1, now = 0;
    for (int i = 0; i < sz(t); i += 2) {
        if (val[t.substr(i, 2)] == 0 && now * 2 == i) {
            now++;
        }
        pos += (pw * val[t.substr(i, 2)]) % mod;
        pos %= mod;
        pw *= 5;
        pw %= mod;
    }
    if (now * 2 == sz(t)) now = k + 1000;
    if (now + 1 < k) {
        cout << -1 << '\n';
        return;
    }
    pw = 4;
    while (--k)  {
        pos = (pos + pw) % mod;
        pw = (pw * 4) % mod;
    }
    cout << pos << '\n';
}

int main() {
    /*
    for (int i = 0; i < (1 << K); ++i) {
        for (int j = 0; j < K; ++j) {
            g[i].insert(j);
        }
    }
    dfs(0);
    */
    int T = 0;
    cin >> T;
    while (T--) solve();
}