#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("stirling.in");
ofstream g("stirling.out");

void s(int n, int k)
{
    int A[n + 1][k + 1];
    A[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= min(i, k); j++)
            A[i][j] = A[i - 1][j - 1] + (i - 1) * A[i - 1][j];
    g << A[n][k] << '\n';
}

void S(int n, int k)
{
    int A[n + 1][k + 1];
    A[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= min(i, k); j++)
            A[i][j] = A[i - 1][j - 1] + j * A[i - 1][j];
    g << A[n][k] << '\n';
}

int main()
{
    int T, x, n, m;
    f >> T;
    while(T--)
    {
        f >> x >> n >> m;
        if(x == 1)
            s(n, m);
        else
            S(n, m);
    }
    f.close();
    g.close();
    return 0;
}