如何用动态规划求解？

TOP_LK

题目描述：
阿宅是一名工程师，平时业余生活就两件事情，玩游戏和看美剧。好不容易迎来了n(n是偶数)天假期，阿宅惯例是宅着家里，玩游戏，看美剧。他想雨露均沾对待这两件事情，每件事情都刚好占用n/2天时间。但是持续做一件事情久了人们就会感到厌倦，阿宅也不例外，他不想连续d天在做同一件事情(如果在某一件事情花费的时间已经到n/2天了，剩下时间只能做另外一件事情，这种情况除外)。阿宅同时还希望第一天的选择和最后一天的选择不一样。现在他想知道有多少种方案安排自己的时间，来最大程度的愉悦自己。聪明的你帮他算一算吧。

输入
第一行输入一个数字t, 表示接下来有t行输入数据，每行输入n, d两个数字。取值范围：1<=t<=1000,  2<=n<=64,  n保证是偶数，1<=d<=n/2。

输出
输出t行，每行表示答案


样例输入
2
2   1
6   2
样例输出
2
10

fc1735

每天只有两种选择，从第一天迭代到最后一天，纪录前一天的选择