105027 - 组合数问题

从（1，2，3）三个人中选择两个人参加比赛可以有（1，2），（1，3），（2，3）这三种方案。我们称从n个人中选择m个人参加比赛的方案数为组合数C（n，m）。组合数的一般公式为：C(n,m)=\dfrac{n!}{m!(n-m)!}，规定C（n，0）＝1。

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

第一行为两个整数T（1\le T\le10 000）和k（1＜k\le21），其中T为测试组数。

接下来T行中，每行有两个整数即n（3\le n\le2 000）和m（3\le m\le2 000）。

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

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