组合数$C_n^m$表示的是从n个物品中选出m个物品的方案数。举个例子，从(1, 2, 3)三个物品中选择两个物品可以有(1, 2), (1, 3), (2, 3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：
$C_n^m = \frac{n!}{m!(n-m)!}$
其中 n! = 1 x 2 x ... x n。
小葱想知道如果给定n, m和k，对于所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足$C_i^j$是k的倍数。
第一行有两个整数t, k，其中t代表该测试点总共有多少组测试数据，k的意义见【问题描述】。
接下来t行每行两个整数n, m，其中n, m的意义见【问题描述】。
t行，每行一个整数代表所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足$C_i^j$是k的倍数。
1 2 3 3 2 5 4 5 6 7
1 0 7
【样例1说明】
在所有可能的情况中，只有$C_2^1=2$是2的倍数。
【子任务】
| 测试点 | n | m | k | t |
|---|---|---|---|---|
| 1 | ≤3 | ≤3 | =2 | =1 |
| 2 | =3 | ≤10000 | ||
| 3 | ≤7 | ≤7 | =4 | =1 |
| 4 | =5 | ≤10000 | ||
| 5 | ≤10 | ≤10 | =6 | =1 |
| 6 | =7 | ≤10000 | ||
| 7 | ≤20 | ≤100 | =8 | =1 |
| 8 | =9 | ≤10000 | ||
| 9 | ≤25 | ≤2000 | =10 | =1 |
| 10 | =11 | ≤10000 | ||
| 11 | ≤60 | ≤20 | =12 | =1 |
| 12 | =13 | ≤10000 | ||
| 13 | ≤100 | ≤25 | =14 | =1 |
| 14 | =15 | ≤10000 | ||
| 15 | ≤60 | =16 | =1 | |
| 16 | =17 | ≤10000 | ||
| 17 | ≤2000 | ≤100 | =18 | =1 |
| 18 | =19 | ≤10000 | ||
| 19 | ≤2000 | =20 | =1 | |
| 20 | =21 | ≤10000 |
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||