Problem Background

NOIP2016 Senior Group D2T1

Problem Description

The combination number $\binom{n}{m}$ represents the number of ways to choose $m$ items from $n$ items. For example, choosing two items from the set $(1,2,3)$ can be done in three ways: $(1,2)$, $(1,3)$, and $(2,3)$. According to the definition of combination numbers, we can provide a general formula for calculating $\binom{n}{m}$:

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

where $n! = 1 \times 2 \times \cdots \times n$; specifically, $0! = 1$.

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

Input Format

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

The next $t$ lines each contain two integers $n$ and $m$, where $n$ and $m$ are as described in the problem statement.

Output Format

Output $t$ lines, each containing a single integer representing the number of pairs $(i, j)$ for all $0 \leq i \leq n, 0 \leq j \leq \min(i, m)$ that satisfy $k \mid \binom{i}{j}$.

Sample Input and Output

Sample Input #1

1 2
3 3

Sample Output #1

1

Sample Input #2

2 5
4 5
6 7

Sample Output #2

0
7

Notes

Sample 1 Explanation

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

Subtasks

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

见题面 Input 部分

见题面 Output 部分