#include<fstream>
#define max_n 210
#define p 98999
using namespace std;
int s[max_n][max_n],S[max_n][max_n];
bool done[max_n][max_n];
void do_it(int i, int j)
{
	if(done[i][j])
		return;
	if(i==j)
	{
		done[i][j]=s[i][j]=S[i][j]=1;
		return;
	}
	do_it(i-1,j-1);
	do_it(i-1,j);
	s[i][j]=(s[i-1][j-1]-(i-1)*s[i-1][j])%p;
	S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%p;
	done[i][j]=1;
}
int main()
{
	int t,x,n,m;
	ifstream read ("stirling.in");
	ofstream write ("stirling.out");
	for(int i=1;i<max_n;++i)
		done[i][0]=1;
	read>>t;
	while(t--)
	{
		read>>x>>n>>m;
		do_it(n,m);
		if(x==1)
			write<<s[n][m]<<'\n';
		else
			write<<S[n][m]<<'\n';
	}
	return 0;
}