#include <bits/stdc++.h>
using namespace std;

#line 2 "math/enumerate-quotient.hpp"

#line 2 "math/isqrt.hpp"

#include <cmath>
using namespace std;

// floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す)
long long isqrt(long long n) {
  if (n <= 0) return 0;
  long long x = sqrt(n);
  while ((x + 1) * (x + 1) <= n) x++;
  while (x * x > n) x--;
  return x;
}
#line 4 "math/enumerate-quotient.hpp"

namespace EnumerateQuotientImpl {
long long fast_div(long long a, long long b) { return 1.0 * a / b; };
long long slow_div(long long a, long long b) { return a / b; };
}  // namespace EnumerateQuotientImpl

// { (q, l, r) : forall x in (l,r], floor(N/x) = q }
// を引数に取る関数f(q, l, r)を渡す。範囲が左に半開なのに注意
// 商は小さい方から走査する
template <typename T, typename F>
void enumerate_quotient(T N, const F& f) {
  T sq = isqrt(N);

#define FUNC(d)                       \
  T upper = N, quo = 0;               \
  while (upper > sq) {                \
    T thres = d(N, (++quo + 1));      \
    f(quo, thres, upper);             \
    upper = thres;                    \
  }                                   \
  while (upper > 0) {                 \
    f(d(N, upper), upper - 1, upper); \
    upper--;                          \
  }

  if (N <= 1e12) {
    FUNC(EnumerateQuotientImpl::fast_div);
  } else {
    FUNC(EnumerateQuotientImpl::slow_div);
  }
#undef FUNC
}

/**
 *  @brief 商の列挙
 */
 
 #line 2 "modint/modint.hpp"

template <int mod>
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int)(1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }
  ModInt operator+() const { return ModInt(*this); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }

  int get() const { return x; }

  static constexpr int get_mod() { return mod; }
};

/**
 * @brief modint
 */
 
 #line 2 "multiplicative-function/divisor-multiple-transform.hpp"

#include <map>
#include <vector>
using namespace std;

#line 2 "prime/prime-enumerate.hpp"

// Prime Sieve {2, 3, 5, 7, 11, 13, 17, ...}
vector<int> prime_enumerate(int N) {
  vector<bool> sieve(N / 3 + 1, 1);
  for (int p = 5, d = 4, i = 1, sqn = sqrt(N); p <= sqn; p += d = 6 - d, i++) {
    if (!sieve[i]) continue;
    for (int q = p * p / 3, r = d * p / 3 + (d * p % 3 == 2), s = 2 * p,
             qe = sieve.size();
         q < qe; q += r = s - r)
      sieve[q] = 0;
  }
  vector<int> ret{2, 3};
  for (int p = 5, d = 4, i = 1; p <= N; p += d = 6 - d, i++)
    if (sieve[i]) ret.push_back(p);
  while (!ret.empty() && ret.back() > N) ret.pop_back();
  return ret;
}
#line 8 "multiplicative-function/divisor-multiple-transform.hpp"

struct divisor_transform {
  template <typename T>
  static void zeta_transform(vector<T> &a) {
    int N = a.size() - 1;
    auto sieve = prime_enumerate(N);
    for (auto &p : sieve)
      for (int k = 1; k * p <= N; ++k) a[k * p] += a[k];
  }
  template <typename T>
  static void mobius_transform(vector<T> &a) {
    int N = a.size() - 1;
    auto sieve = prime_enumerate(N);
    for (auto &p : sieve)
      for (int k = N / p; k > 0; --k) a[k * p] -= a[k];
  }

  template <typename I, typename T>
  static void zeta_transform(map<I, T> &a) {
    for (auto p = rbegin(a); p != rend(a); p++)
      for (auto &x : a) {
        if (p->first == x.first) break;
        if (p->first % x.first == 0) p->second += x.second;
      }
  }
  template <typename I, typename T>
  static void mobius_transform(map<I, T> &a) {
    for (auto &x : a) {
      for (auto p = rbegin(a); p != rend(a); p++) {
        if (x.first == p->first) break;
        if (p->first % x.first == 0) p->second -= x.second;
      }
    }
  }
};

struct multiple_transform {
  template <typename T>
  static void zeta_transform(vector<T> &a) {
    int N = a.size() - 1;
    auto sieve = prime_enumerate(N);
    for (auto &p : sieve)
      for (int k = N / p; k > 0; --k) a[k] += a[k * p];
  }
  template <typename T>
  static void mobius_transform(vector<T> &a) {
    int N = a.size() - 1;
    auto sieve = prime_enumerate(N);
    for (auto &p : sieve)
      for (int k = 1; k * p <= N; ++k) a[k] -= a[k * p];
  }

  template <typename I, typename T>
  static void zeta_transform(map<I, T> &a) {
    for (auto &x : a)
      for (auto p = rbegin(a); p->first != x.first; p++)
        if (p->first % x.first == 0) x.second += p->second;
  }
  template <typename I, typename T>
  static void mobius_transform(map<I, T> &a) {
    for (auto p1 = rbegin(a); p1 != rend(a); p1++)
      for (auto p2 = rbegin(a); p2 != p1; p2++)
        if (p2->first % p1->first == 0) p1->second -= p2->second;
  }
};

/**
 * @brief 倍数変換・約数変換
 * @docs docs/multiplicative-function/divisor-multiple-transform.md
 */
 

using mint = ModInt<998244353>;

struct query { int n, m, k; };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T; cin >> T;
	
	vector<query> queries(T);
	int M = 0;
	
	for (int i=0; i<T; i++) {
		cin >> queries[i].n >> queries[i].m >> queries[i].k;
		M = max(M, queries[i].m);
	}
	
	vector<vector<mint>> pref(10, vector<mint>(M+10));
	
	for (int i=1; i<=M; i++) {
		mint pow = 1;
		for (int j=0; j<10; j++) {
			pow *= i;
			pref[j][i] = pow;
		}
	}
	
	for (int i=0; i<10 ;i++) {
		divisor_transform::mobius_transform(pref[i]);
		for (int j=1; j<=M; j++) pref[i][j] += pref[i][j-1];
	}
	
	for (int i=0; i<T; i++) {
		auto [n, m, k] = queries[i];
		mint ans = 0;
		enumerate_quotient(m, [&](long long q, long long l, long long r) { ans+= (pref[k-1][r]-pref[k-1][l])*mint(q).pow(n);});
		cout << ans << '\n';
	}
}