#include <cstdio>
#include <iostream>

const unsigned n=200;
const int MODULO=98999;
int s[n+1][n+1], S[n+1][n+1];

void preprocess(){
	s[1][1]=1; S[1][1]=1;
	for(unsigned i=2;i<=n;++i)
		for(unsigned j=1;j<=i;++j){
			s[i][j]=(s[i-1][j-1]-(i-1)*s[i-1][j])%MODULO;
			S[i][j]=(j*S[i-1][j]+S[i-1][j-1])%MODULO;
		}
}

int main(){
	std::freopen("stirling.in","r",stdin);
	std::freopen("stirling.out","w",stdout);

	preprocess();

	int t; scanf("%d",&t);
	while(t--){
		unsigned sp,n,k;
		scanf("%d %d %d",&sp,&n,&k);
		if(sp==1) printf("%d\n",s[n][k]);
		else printf("%d\n",S[n][k]);
	}

}