把 $ M $ 个同样的苹果放在 $ N $ 个同样的盘子里，允许有的盘子空着，问共有多少种不同的放法？

注：5，1，1 和 1，5，1 是同一种放法（因为盘子相同，顺序无关）。

第一行包含一个整数 $ t （ 0 < t \le 20 ）$，表示测试数据的组数。

接下来 $ t $ 行，每行包含两个整数 $ M $ 和 $ N （ 1 \le M, N \le 10 ）$，分别表示苹果数和盘子数。

对于每组数据，输出一行一个整数，表示对应的放法总数 $ K $。

## 数据范围与约定

- $ 1 \le M, N \le 10 $
- $ 0 < t \le 20 $

## 提示

这是一个经典的递归/动态规划问题。

设 $ f(m, n) $ 表示将 $ m $个苹果放入 $ n $ 个盘子中的方法数。考虑两种情况：

1. 至少有一个盘子空着：此时方法数为 $ f(m, n-1) $。
2. 所有盘子都非空：则每个盘子先放一个苹果，剩下 $ m-n $ 个苹果随意放入 $ n $ 个盘子，方法数为 $ f(m-n, n) $。

因此递推式：

$f(m,n)=\begin{array}{l}  
  \left\{\begin{matrix} 
  f(m, n) = 1, m = 0 或 n = 1 \\ 
  f(m, m), n > m \\ 
  f(m, n-1) + f(m-n, n), m \ge n 
\end{matrix}\right.    
\end{array}  $

- 当 $ m = 0 $ 时，只有一种放法（所有盘子都空）；
- 当 $ n = 1 $ 时，只有一种放法（所有苹果放在这一个盘子里）；
- 当 $ n > m $ 时，空盘子不影响结果，等价于 $ f(m, m) $。

用递归或动态规划均可，由于数据范围很小，递归即可。