#include <fstream>

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

int stirlingI(int, int);
int stirlingII(int, int);

int s[205][205], S[205][205];

int main()
{
    int t;
    fin >> t;

    for (int i = 1; i <= 200; i++)
        for (int j = 1; j <= 200; j++)
            S[i][j] = s[i][j] = -1;

    for (int i = 1; i <= t; i++)
    {
        int x, n, m;
        fin >> x >> n >> m;

        if (x == 1)
            fout << stirlingI(n, m) << '\n';
        else
            fout << stirlingII(n, m) << '\n';
    }
    return 0;
}

int stirlingI(int n, int k)
{
    if (s[n][k] != -1)
        return s[n][k];

    if (n == k)
    {
        s[n][k] = 1;
        return s[n][k];
    }

    if (k > n)
    {
        s[n][k] = 0;
        return  s[n][k];
    }

    s[n][k] = stirlingI(n - 1, k - 1) % 98999 - (n - 1) * stirlingI(n - 1, k) % 98999;
    return s[n][k] % 98999;
}

int stirlingII(int n, int k)
{
    if (S[n][k] != -1)
        return S[n][k];

    if (n == k)
    {
        S[n][k] = 1;
        return S[n][k];
    }

    if (n >= 1 && k == 1)
    {
        S[n][k] = 1;
        return S[n][k];
    }

    S[n][k] = stirlingII(n - 1, k - 1) % 98999 + k * stirlingII(n - 1, k) % 98999;
    return S[n][k] % 98999;
}