#include<bits/stdc++.h>
#define int long long
#define ll long long
#define db double
#define pii pair<int, int>
using namespace std;
const int N = 2e6 + 999, mod = 1e9+7;
int pos[N], p[N], pos1[N];
void solve(){
    string s, t;
    cin >> s >> t;
    reverse(s.begin(), s.end());
    reverse(t.begin(), t.end());
    s.push_back('0'), t.push_back('0');
    while(s.length() < t.length())
        s.push_back('0');
    while(t.length() < s.length())
    t.push_back('0');
    int lt = t.size(), ls = s.size();
    for (int i = 0; i < min(ls, lt); i++)
        t[i] = (t[i] - '0') ^ (s[i] - '0') + '0';
    int k;
    cin >> k;
    int ans = 0;
    for (int i = lt - 1; i >= 2; i--){
        if(t[i] == '1'){
            ans += pos[i];
            ans %= mod;
        }
    }
    int lb = 1e6;
    for (int i = 0; i < lt; i++)
        if(t[i] == '1'){
            lb = i;
            break;
        }
    if(lb / 2 + 1 >= k){
        if(t[0] == '1' && t[1] == '1')
            ans += 2;
        else if(t[0] == '1')
            ans += 1;
        else if(t[1] == '1')
            ans += 3;
        else
            ans += pos1[k];
        ans %= mod;
    }
    else
        ans = -1;
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    p[0] = 1;
    for (int i = 1; i <= 1e6; i++)
        p[i] = p[i - 1] * 4 % mod;
    pos[0] = 1;
    pos[1] = 3;
    for (int i = 2; i <= 1e6; i++){
        if(i & 1)
            pos[i] = (p[(i + 1) / 2] + mod - 1) % mod;
        else
            pos[i] = (pos[i - 2] + p[i  / 2]) % mod;
    }
    pos1[1] = 0;
    for (int i = 2; i <= 1e6; i++)
        pos1[i] = (pos[(i - 1) * 2] - 1 + mod) % mod;
        int T;
    cin >> T;
    while(T--)
        solve();
    return 0;
}