Description

The binomial coefficient $\binom{n}{m}$ represents the number of ways to choose $m$ items from $n$ items. For example, when choosing two items from three items $(1, 2, 3)$, there are three choices: $(1, 2)$, $(1, 3)$, and $(2, 3)$. By definition, the general formula for computing the binomial coefficient $\binom{n}{m}$ is:

where $n!=1\times2\times\cdots\times n$. In particular, $0!=1$.

Xiaocong wants to know, given $n$, $m$, and $k$, among all $0 \leq i \leq n$, $0 \leq j \leq \min \left ( i, m \right )$, how many pairs $(i, j)$ satisfy $k \mid \binom{i}{j}$.

Input Format

The first line contains two integers $t, k$, where $t$ is the number of test cases in this testdata, and $k$ is as described in the problem.

Each of the next $t$ lines contains two integers $n, m$, where $n$ and $m$ are as described in the problem.

Output Format

Output $t$ lines. Each line contains a single integer representing how many pairs $(i, j)$ among all $0 \leq i \leq n$, $0 \leq j \leq \min \left ( i, m \right )$ satisfy $k \mid \binom{i}{j}$.

1 2
3 3

1

2 5
4 5
6 7

0
7

Hint

Sample 1 Explanation.

Among all possible cases, only $\binom{2}{1} = 2$ is a multiple of $2$.

Subtasks.

Constraints.

For all testdata, it is guaranteed that $0 \leq n, m \leq 2 \times 10^3$, $1 \leq t \leq 10^4$.

Translated by ChatGPT 5