Description

把M个相同的苹果放在N个相同的盘子里，同意有的盘子空着不放，问共同拥有多少种不同的分法？（用K表示）5。1。1和1。5，1 是同一种分法。

Input

第一行是測试数据的数目t（0 <= t <= 20）。

下面每行均包括二个整数M和N，以空格分开。1<=M，N<=10。

Output

对输入的每组数据M和N。用一行输出对应的K。

Sample Input

17 3

Sample Output

8

/**poj1664 dp记忆化搜索写法题目大意：中文题不在赘述解题思路：（转）令f(m,n)表示m个苹果放到n个盘子里有多少种放法，以下对不同的情况给予讨论:          (1):当盘子数为1的时候，仅仅有一种放法就是把全部苹果放到一个盘子里。          (2):当苹果数为1的时候，也仅仅有一种放法，注意题目中说明，盘子之间并无顺序,所以无论这个苹果放在哪个盘子里，结果都算一个。          (3):当m
     
      n时，也分两种情况讨论，一种是至少有一个盘子里不放苹果。这样子就相当于f(m,n-1),另外一种是，先取出n个苹果一个盘子里放一个，再将剩下的m-n个苹果放到n个盘子里去，即f(m-n,n);          综上所述得到递归表达式：f(m,n)=1 当 m=1或n=1；                                  f(m,n)=f(m,m) 当m
      
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int n,m;int dp[15][15];int dfs(int n,int m){ if(dp[n][m])return dp[n][m]; if(n==1||m==1) { dp[n][m]=1; return dp[n][m]; } if(n
           
            m) { dp[n][m]=dfs(n,m-1)+dfs(n-m,m); return dp[n][m]; }}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(dp,0,sizeof(dp)); printf("%d\n",dfs(n,m)); } return 0;}