#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 998244353;

int mp[4][4];

i64 power(i64 a, i64 b)
{
    i64 res = 1;
    for( ; b; b >>= 1, a = a * a % P)
        if(b & 1) res = res * a % P;

    return res;
}

void repeater()
{
    std::string s, t; std::cin >> s >> t;
    int k; std::cin >> k;

    if(s == t)
    {
        std::cout << ((power(4, k) - 1) * power(3, P - 2) - 1) % P << "\n";
        return;
    }

    int len = std::max((int)s.size(), (int)t.size());
    len += len & 1;

    std::ranges::reverse(s);
    std::ranges::reverse(t);
    s += std::string(len - (int)s.size(), '0');
    t += std::string(len - (int)t.size(), '0');

    int cnt = 0;
    for(int i = 1; i < len; i += 2)
    {
        if(s[i] != t[i] && s[i - 1] != t[i - 1]) break;
        cnt++;
    }

    if(cnt < k - 1)
    {
        std::cout << -1 << "\n";
        return;
    }

    i64 ans = 0;
    for(i64 i = 1, j = 1; i < len; i += 2, j = j * 5 % P)
    {
        int a = (s[i] - '0') * 2 + (s[i - 1] - '0');
        int b = (t[i] - '0') * 2 + (t[i - 1] - '0');

        ans += mp[a][b] * j;
        ans %= P;
    }
    ans += ((power(4, k) - 1) * power(3, P - 2) - 1) % P;
    ans %= P;
    std::cout << ans << "\n";;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    mp[0][1] = 1, mp[0][2] = 3, mp[0][3] = 2;
    mp[1][0] = 1, mp[1][2] = 2, mp[1][3] = 3;
    mp[2][0] = 3, mp[2][1] = 2, mp[2][3] = 1;
    mp[3][0] = 2, mp[3][1] = 3, mp[3][2] = 1;

    int t; std::cin >> t;
    while(t--) repeater();

    return 0;
}