---
# System prepended metadata

title: 巴斯卡三角形

---

# 巴斯卡三角形
![](https://i.imgur.com/Mx39IYJ.png)
上圖為六層巴斯卡三角形的示意圖，來自 [wiki](https://en.wikipedia.org/wiki/Pascal%27s_triangle)

一種建構巴斯卡三角形的方式如下：

首先第 1 排第 1 個數字為 1，其他數字則為左上方及右上方的數字和（若無左上或右上視為 0），如此遞迴定義即可建構出巴斯卡三角形。

請問你是否能輸出巴斯卡三角形中的某個指定位置呢？

### 輸入說明
輸入一個整數 T 代表有 T 組詢問，每組詢問有 n, m 兩個整數。 其中 T <= 10 且 1 <= m <= n <= 20。

### 輸出說明
巴斯卡三角形第 n 排從左邊數來第 m 個數字。

注意：必須在行尾輸出換行。

### 輸入範例
```
3
1 1
6 3
5 2
```
### 輸出範例
```
1
10
4
```
# Code
```cpp
#include <iostream>

using namespace std;

int Pascal(int n, int m)
{
  if (m == 1 || m == n)
    return 1;
  return Pascal(n - 1, m - 1) + Pascal(n - 1, m);
}

int main()
{
  int T;
  cin >> T;
  for (int i = 0; i < T; i++)
  {
    int n, m;
    cin >> n >> m;
    cout << Pascal(n, m) << "\n";
  }
}
```