#include<bits/stdc++.h>
#include<atcoder/all>
#define chmin(x,y) (x) = min((x),(y))
#define chmax(x,y) (x) = max((x),(y))
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vec vector
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back 
#define eb emplace_back

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
const ll mod = 998244353;
using mint = modint998244353;
const vector<int> dx = {1,0,-1,0}, dy = {0,1,0,-1};
// using Graph = vector<vector<pair<int,ll>>>;
using Graph = vector<vector<int>>;

ll ceill(ll x, ll y){
  ll res = x / y;
  if(x % y != 0) res++;
  return res;
}

mint f(ll X, ll A, ll B, ll K){
  // press A until score becomes ceil(A/B-1),
  // which is the solution of Bx < x + A,
  // then press B
  if(B == 1) return (mint)A * K;

  ll push_A = min(K,max(0LL,ceill(ceill(A - X, (B-1)),A)));
  // cout << push_A << endl;
  mint res = (mint)(X + A) * push_A * ((mint)B).pow(K-push_A);
  return res;
}

int main(){
  // input
  int T;
  cin >> T;
  while(T--){
    ll A,B,K;
    cin >> A >> B >> K;
    if(A == 0){
      //  corner case
      cout << 0 << endl;
    }
    else if(A > 0){
      // A > 0 && B > 0
      if(B > 1){
        cout << f(0,A,B,K).val() << endl;
      }
      else cout << (A * K) % mod << endl;
    }
    else if(A < 0){
      if(B >= 0 || K == 1) cout << 0 << endl;
      else{
        // most crazy
        // "(K-n) * A -> n * B" where n is odd
        // K >= 2 is assured
        if(K % 2)
          cout << f(2*A*B,-2*A,B*B,K/2-1).val() << endl;
        // ll ini = A * B * (K % 2 == 0 ? 2 : 1);
        else
          cout << f(A*B,-2*A,B*B,K/2-1).val() << endl;
      }
    }
  }
  
  // solve
  
  // output
  
}