#include <bits/stdc++.h>

using namespace std;

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

int speta_1(int a, int b)
{
    if(a == 0 || b == 0)
        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) ) % 98999;
}

int speta_2(int a, int b)
{
    if(a == 0 || b == 0)
        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)) % 98999;
}

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

    fin >> n;

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

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

        n--;
    }

    return 0;
}