#include<stdio.h>

const int MOD=98999;

int apel_s(int n,int m)
{
	if( !n || !m )
		return 0;
	if( n<m )
		return 0;
	if( n==1 && m==1 )
		return 1;
	return ( apel_s(n-1,m-1) - (n-1)*apel_s(n-1,m) )%MOD;
}

int apel_S(int n,int m)
{
	if( !n || !m )
		return 0;
	if( n<m )
		return 0;
	if( n==1 && m==1 )
		return 1;
	return ( apel_S(n-1,m-1) + m*apel_S(n-1,m) )%MOD;
}

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

	int speta,n,m,t;

	scanf("%d",&t);

	while( t-- )
	{
		scanf("%d%d%d",&speta,&n,&m);
		if(speta==1)
			printf("%d\n",apel_s(n,m));
		if(speta==2)
			printf("%d\n",apel_S(n,m));
	}

	return 0;
}