#include <stdio.h>

using namespace std;

int s[210][210];
int S[210][210];

void ordins()
{
    s[1][1]=1;
    for(int i=2;i<203;++i)
    {
        for(int j=1;j<203;++j)
        {
            s[i][j]=s[i-1][j-1]-(i-1)*s[i-1][j];
            s[i][j]%=98999;
        }
    }
}

void ordinS()
{
    S[1][1]=1;
    for(int i=2;i<203;++i)
    {
        for(int j=1;j<203;++j)
        {
            S[i][j]=S[i-1][j-1]+j*S[i-1][j];
            S[i][j]%=98999;
        }
    }
}


int main()
{
    freopen("stirling.in","r",stdin);
    freopen("stirling.out","w",stdout);
    ordins();
    ordinS();
    int t;
    scanf("%d",&t);
    for(;t;--t)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        if(x==1)
        {
            printf("%d\n",s[y][z]);
        }
        else
            printf("%d\n",S[y][z]);
    }

    return 0;
}