放苹果

Input

Output

Sample Input

1
7 3

Sample Output

8


    int t = 0,m,n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> m >> n;
        cout << apple(n, m) << endl;
    }

int apple(int n,int m)//n个盘子放m个苹果
{
    if (m == 0 || n == 1)//没有苹果了，或只有一个盘子了，递归出口
        return 1;
    if (m < n)
        return apple(m, m);//苹果数小于盘子数，多于的盘子肯定为空
    else
        return apple(n, m - n) + apple(n - 1, m);
    /*分两种情况相加
    1.盘子都不为空，那么就至少有一个苹果，即每个盘子放一个
    转变为n个盘子放m-n个苹果的子问题
    2.让其中一个盘子不放
    */
}