《算法竞赛宝典》语言及算法入门(公开课程)

【例题描述】组合数问题（problem.cpp）

从（1，2，3）三个人中选择两个人参加比赛可以有（1，2），（1，3），（2，3）这三种方案。我们称从n个人中选择m个人参加比赛的方案数为组合数C（n，m）。组合数的一般公式为：

规定C（n，0）＝1。

现给定n，m和k，对于所有的i和j（0≤i≤n，0≤j≤i），问有多少C（i，j）是k的倍数。

【输入格式】

第一行为两个整数T（1≤T≤10000）和k（1＜k≤21），其中T为测试组数。

接下来T行中，每行有两个整数即n（3≤n≤2000）和m（3≤m≤2000）。

【输出格式】

输出T行，每行为一个整数，即有多少C（i，j）是k的倍数。

【输入样例】

1 2

3 3

【输出样例】

1

【样例说明】

只有C（2，1）＝2是2的倍数。