#include <bits/stdc++.h>

using namespace std;

ifstream fin("stirling.in");
ofstream fout("stirling.out");

#define MAX 98999

int speta_1(int a, int b)
{
    if( !a || !b )
        return 0;
    if(a < b)
        return 0;
    if(a == 1 && b == 1)
        return 1;

    return (speta_1(a - 1, b - 1) - (a - 1) * speta_1(a - 1, b)) % MAX;
}

int speta_2(int a, int b)
{
    if( !a || !b )
        return 0;
    if(a < b)
        return 0;
    if(a == 1 && b == 1)
        return 1;

    return (speta_1(a - 1, b - 1) + a * speta_1(a - 1, b)) % MAX;
}

int main()
{
    int n, cer, a, b;

    fin >> n;

    while(n)
    {
        fin >> cer >> a >> b;

        if(cer == 1)
            fout << speta_1(a,b) << '\n';
        else
            fout << speta_2(a,b) << '\n';

        n--;
    }

    return 0;
}