다리놓기

#include <iostream>
#include <vector>
 
using namespace std;
 
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    //최대  n개 만큼만 다리를 지을 수 있다. 
    int t;
    cin >> t;
 
    while (t--) {
        int n, m;
        cin >> n >> m;
 
        if (n == m) {
            cout << 1 << '\n';
            continue;
        }
        if (n == 1) {
            cout << m << '\n';
            continue;
        }
        ll dp[31][31] = { {0} };
 
 
        for (int j = 1; j <= m; j++) {
            dp[1][j] = j;
        }
 
        //사이트의 번호보다 큰 다리만 연결 가능 
 
        for (int i = 2; i <= n; i++) {
            for (int k = i; k <= m; k++) {
                dp[i][k] = dp[i - 1][k-1] + dp[i][k-1];
 
            }
        }
        cout << dp[n][m] << '\n';
 
    }
 
    return 0;
}