U428307 杨辉三角

杨辉三角： >$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1$ > >$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ \ 1$ > >$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ 2\ \ \ 1$ > >$\ \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ 3\ \ \ 3\ \ \ 1$ > >$\ \ \ \ \ \ \ \ \ \ 1\ \ \ 4\ \ \ 6\ \ \ 4\ \ \ 1$ > >$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ……$

杨辉三角上的数字与二项式展开的系数相关，例如： >$(a+b)^0=1$，而三角中第$(0+1)$行数为$1$ > >$(a+b)^1=a+b$，而三角中第$(1+1)$行数为$1,1$ > >$(a+b)^2=a^2+2ab+b^2$，而三角中第$(2+1)$行数为$1,2,1$ > >$(a+b)^3=a^3+3a^2b+3ab^2+b^3$，而三角中第$(3+1)$行数为$1,3,3,1$ > >…… 以此类推，所以根据杨辉三角可以直接写出$(a+b)^n$的展开式。 进一步观察，还能发现，杨辉三角中两腰都是$1$，内部的数字都是由它肩上的两个数相加而成，又由杨辉三角与二项式系数有关，所以，我们可以扩充杨辉三角： >行数 $|$ > >$\ \ \ \ \ \ \ |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ……$ > >$-2\ \ |\ 0\ \ \ 0\ \ \ 0\ \ \ 0\ \ \ 1\ \ \ -2\ \ \ 3\ \ \ -4$ > >$-1\ \ |\ \ \ \ 0\ \ \ 0\ \ \ 0\ \ \ 1\ \ \ -1\ \ \ 1\ \ \ -1$ > >$0\ \ \ \ \ |\ 0\ \ \ 0\ \ \ 0\ \ \ 1\ \ \ \ \ 0\ \ \ \ \ \ 0\ \ \ \ \ \ 0\ \ \ \ \ 0$ > >$1\ \ \ \ \ |\ \ \ \ 0\ \ \ 0\ \ \ 1\ \ \ 1\ \ \ \ \ \ 0\ \ \ \ \ \ 0\ \ \ \ \ \ 0$ > >$2\ \ \ \ \ |\ 0\ \ \ \ 0\ \ \ 1\ \ \ 2\ \ \ 1\ \ \ \ \ \ 0\ \ \ \ \ \ 0\ \ \ \ \ \ 0$ > >$3\ \ \ \ \ |\ \ \ \ 0\ \ \ 1\ \ \ 3\ \ \ 3\ \ \ \ 1\ \ \ \ \ \ \ 0\ \ \ \ \ \ 0$ > >$4\ \ \ \ \ |\ 0\ \ \ \ 1\ \ \ 4\ \ \ 6\ \ \ 4\ \ \ \ \ 1\ \ \ \ \ \ \ 0\ \ \ \ \ \ 0$ > >$\ \ \ \ \ \ \ |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ……$ 将它列成表，还可得 | 行/列 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | **-3** | 0 | 0 | 0 | 1 | -3 | 6 | -10 | | **-2** | 0 | 0 |0 | 1 | -2 | 3 | -4 | | **-1** | 0 | 0 | 0 | 1| -1 | 1 | -1 | | **0** | 0 | 0| 0 | 1 | 0 | 0 | 0 | | **1** | 0 | 0 | 0 | 1 | 1 | 0 | 0 | | **2** | 0 | 0 | 0 | 1 | 2 | 1 | 0 | | **3** | 0 | 0 | 0 | 1 | 3 | 3 | 1 | 所以，杨辉三角还可以表述为满足二维列表$M(行,列)$中： 1. $\forall n \in \Z$，$M(0,n)=1$ 2. $\forall n \in \complement _\Z \{ 0 \}$, $M(n,0)=0$ 3. $\forall i,j \in \Z$，$M(i,j)=M(i-1,j-1)+M(i-1,j)$ 例如，$M(2,1)=2=M(1,0)+M(1,1)$

输入共$T+1$行。 第一行一个整数$T$，表示共有$T$个测试数据。 接下来$T$行，第$n$行两个整数$i_n,j_n$.

输出共$T$行 第$n$行输出一个整数，表示$M(i_n,j_n)$的值

对于$50\%$的数据，$-10≤i_n,j_n≤10,1≤T≤10$； 对于$100\%$的数据，$-50≤i_n,j_n≤50,1≤T≤20$.