#include <cstdio>
using namespace std;
int a,speta,n,k,T,i;
int s(int n,int k)
{

    if (k==n) return +1;
    if (k==1) return +1;
    return +(s(n-1,k-1)+(n-1)*s(n-1,k))%98999;
}
int S(int n,int k)
{
    if (k==n) return +1;
    if (k==1) return +1;
    return +(S(n-1,k-1)+k*S(n-1,k))%98999;
}
using namespace std;
int main()
{
    freopen("stirling.in","r",stdin);
    freopen("stirling.out","w",stdout);
    scanf("%d",&T);
    for (i=1; i<=T ;i++)
    {
        scanf("%d%d%d",&speta,&n,&k);
        if (speta==1)
            {
                a=s(n,k)%98999;
                if ((n-k)%2!=0) a*=-1;
            }

        if (speta==2) a=S(n,k)%98999;
        printf("%d\n",a);
    }
}