#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
using ll=long long;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int ttt;
	cin>>ttt;
	int maxm=1000000;
	vector<vector<mint>> f(11,vector<mint>(maxm+1));
	vector<vector<mint>> fsum(11,vector<mint>(maxm+2));
	for(int i=1;i<=10;i++){
		f[i][1]=1;
		fsum[i][2]=1;
		for(int j=2;j<=maxm;j++){
			f[i][j]+=((mint)j).pow(i)-1;
			for(int l=j+j;l<=maxm;l+=j)f[i][l]-=f[i][j];
			fsum[i][j+1]=fsum[i][j]+f[i][j];
		}
	}
	while(ttt--){
		int n,m,k;
		cin>>n>>m>>k;
		vector<int> v;
		int t=1;
		while(t<=m){
			v.push_back(m/t);
			t=(m/(m/t))+1;
		}
		mint ans=0;
		//for(int i=1;i<=m;i++)cout<<f[k][i].val()<<" ";
		//cout<<endl;
		for(int x:v){
			int l=m/(x+1)+1;
			int r=m/x+1;
			//cout<<x<<" "<<l<<" "<<r<<endl;
			ans+=(fsum[k][r]-fsum[k][l])*((mint)x).pow(n);
		}
		cout<<ans.val()<<endl;

	}
}