题目描述

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

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

$$\red{C_n ^ m = \frac{n!}{m!(n - m)!}}$$

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

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

输入格式

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

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

输出格式

$\red{t }$ 行，每行一个整数代表答案。

样例

样例输入 1

1 2
3 3

样例输出 1

1

样例输入 2

2 5
4 5
6 7

样例输出 2

0
7

提示

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