#include <cstdio>
#include <cassert>

int s2[205][205], s1[205][205];
bool computed2[205][205], computed1[205][205];
const int mod = 98999;

int stirling2(int n, int k) // put n balls in k boxes
{
  assert(n >= 0 && k >= 0 && "stirling2 failed");
  if (n == 0 && k == 0) return 1; // 0 balls in 0 boxes is 1 way - the empty way
  if (n < k) return 0; // fewer balls then boxes
  if (k == 0 && n > 0) return 0; // no boxes but there are elements

  if (computed2[n][k])
    return s2[n][k];
  s2[n][k] = (stirling2(n - 1, k - 1) // put the n'th in a new box
	      + stirling2(n - 1, k) * k) % mod; // put the n'th in one of the existing k boxes
  computed2[n][k] = true;
  return s2[n][k];
}

int stirling1(int n, int k) // number of permutations with n elements and k permutation cycles
{
  assert(n >= 0 && k >= 0 && "stirling 1 failed");
  if (n == 0 && k == 0) return 1; // 0 elements and 0 cycles - the empty permutation
  if (n < k) return 0; // fewer elements than cycles
  if (k == 0 && n > 0) return 0; // no cycles but there are elements
  
  if (computed1[n][k])
    return s1[n][k];
  s1[n][k] = (stirling1(n - 1, k - 1) // put the n'th element on the nth position (new cycle)
	      - stirling1(n - 1, k) * (n - 1) ) % mod; // extend one of the existing cycles
  computed1[n][k] = true;
  return s1[n][k];
}

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

  int T;
  scanf("%d", &T);
  while (T--) {
    int op, n, k;
    scanf("%d%d%d", &op, &n, &k);
    if (op == 1)
      printf("%d\n", stirling1(n, k));
    else
      printf("%d\n", stirling2(n, k));
  }
  
}