#include <cstdio>
#define MOD 98999

int StirlingI(int N, int K){

    if(N == 0 || K == 0) return 0;
    if(N < K) return 0;
    if(N == 1 && K == 1) return 1;
    return (StirlingI(N - 1, K - 1) - (N - 1) * StirlingI(N - 1, K)) % MOD;
}

int StirlingII(int N, int K){

    if(N == 0 || K == 0) return 0;
    if(N < K) return 0;
    if(N == 1 && K == 1) return 1;
    return (StirlingII(N - 1, K - 1) + K * StirlingII(N - 1, K)) % MOD;
}

int main(){

    freopen("stirling.in", "r", stdin);
    freopen("stirling.out", "w", stdout);

    int T, speta, N, K;

    scanf("%d", &T);

    while(T--){
        scanf("%d %d %d", &speta, &N, &K);

        if(speta == 1) printf("%d\n", StirlingI(N, K));
        if(speta == 2) printf("%d\n", StirlingII(N, K));
    }
    return 0;
}