该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile2361.zip](file://AdditionalFile2361.zip?type=additional_file)

#2361. 「NOIP2016」组合数问题

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

组合数表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2)$，$(1, 3)$，$(2, 3)$ 这三种选择方法。

根据组合数的定义，我们可以给出计算组合数的一般公式：

其中 $n! = 1 \times 2 \times \cdots \times n$。

小葱想知道如果给定 $n$，$m$ 和 $k$，对于所有的 $0 \leq i \leq n$，$0 \leq j \leq \min(i, m)$ 有多少对 $(i, j)$ 满足 $C_i ^ j$ 是 $k$ 的倍数。

输入格式

第一行有两个整数 $t$，$k$，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见 「题目描述」。

接下来 $t$ 行每行两个整数 $n$，$m$，其中 $n$，$m$ 的意义见「题目描述」。

输出格式

$t$ 行，每行一个整数代表所有的 $0 \leq i \leq n$，$0 \leq j \leq \min(i, m)$ 有多少对 $(i, j)$ 满足 $C_i ^ j$ 是 $k$ 的倍数。

样例 1

输入

1 2
3 3

输出

1

样例 2

输入

2 5
4 5
6 7

输出

0
7

数据范围与提示

$3 \leq n, m \leq 2000, 2 \leq k \leq 21, 1 \leq t \leq 10000$