#include <bits/stdc++.h>
#include <vector>
using i80 = __int128;
using i64 = long long;
using f80 = long double;
constexpr const i64 mod = 1e9 + 7;
const i64 inv3 = 333333336;
i64 pw(i64 x, i64 k) {
    i64 z = 1;
    while (k) {
        if (k & 1) {
            z = z * x % mod;
        }
        x = x * x % mod;
        k >>= 1;
    }
    return z;
}
i64 p(i64 x) {
    return (pw(4, x) * (1 + inv3) % mod - inv3 + mod) % mod;
}
void work() {
    std::string s, t;
    int k;
    std::cin >> s >> t >> k;
    std::reverse(s.begin(), s.end());
    std::reverse(t.begin(), t.end());
    int n = std::max(s.size(), t.size()) / 2 + 3;
    std::vector<int> a(n);
    for (int i = 0; i < (int)s.size(); ++i) {
        a[i / 2] ^= (s[i] == '1') * (i % 2 == 1 ? 2 : 1);
    }
    for (int i = 0; i < (int)t.size(); ++i) {
        a[i / 2] ^= (t[i] == '1') * (i % 2 == 1 ? 2 : 1);
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            ++cnt;
        }
        if (a[i] == 2) {
            a[i] = 3;
        } else if (a[i] == 3) {
            a[i] = 2;
        }
        // std::cout << a[i] << ",\n"[i == n - 1];
    }
    if (cnt == 0) {
        std::cout << (p(k - 1) - 1 + mod) % mod << "\n";
        return;
    }
    if (cnt == 1) {
        if (k > 2) {
            std::cout << "-1\n";
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (a[i]) {
                if (i == 0) {
                    if (k == 2) {
                        std::cout << "-1\n";
                    } else {
                        std::cout << a[i] << "\n";
                    }
                    return;
                }
                i64 ans = p(i) * a[i] % mod;
                // std::cout << ans << "\n";
                if (k == 2) {
                    ans = (ans + p(i) - 1 + mod) % mod;
                }
                std::cout << ans << "\n";
                return;
            }
        }
    }
    if (k > 1) {
        std::cout << "-1\n";
        return;
    }
    i64 ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        ans = (ans + p(i) * a[i]) % mod;
    }
    std::cout << ans << "\n";
    return;
}
void init() {
}
int main() {
    init();
    std::ios::sync_with_stdio(false);
    // std::cin.tie(nullptr), std::cout.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) {

        work();
    }

    return 0;
}
/*

*/