暂无测试数据。

组合数 $C_n^m$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2),(1, 3),(2, 3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：

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

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

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

输入格式

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

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

输出格式

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

数据范围

1 2
3 3

1

2 5
4 5
6 7

0
7