#include <iostream>
#include <math.h>
#define ll long long
#define MOD 998244353
using namespace std;

ll f(ll a) {
    return a%MOD;
}

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

    int t;
    cin >> t;

    for(int i=0; i<t; i++) {
        ll a, b, m;
        cin >> a >> b >> m;

        if(m==0) {
            if(a+b==0) cout << 0;
            else cout << 1;
        }
        else if(b==0) {
            if(a==0) cout << f(m);
            else if(a==1) cout << f(f(m*2+1)*f(m*2+1));
            else cout << f(m*2+1);
        }
        else if(a==0) {
            if(b==1) cout << f(f((m/2)*2+1)*f(m*2+1)); //i^i:real
            else cout << f((m/2)*2+1); // (2i)^i:not real
        }
        else if(a==b) {
            cout << f((m/4)*2+1);
        }
        else cout << 1;
        cout << '\n';
    }
}