The binomial coefficient $C_n^m$ represents the number of ways to choose $m$ items from $n$ items. For example, choosing two items from the three items $(1, 2, 3)$ can be done in $(1, 2), (1, 3), (2, 3)$, which are $3$ ways. Based on the definition of binomial coefficients, we can provide the general formula for $C_n^m$:

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

where $n! = 1 \times 2 \times \dots \times n$.

Given $n, m$ and $k$, for all $0 \le i \le n, 0 \le j \le \min(i, m)$, how many pairs $(i, j)$ satisfy that $C_i^j$ is a multiple of $k$?

Input

The first line contains two integers $t, k$, where $t$ is the total number of test cases, and $k$ is as defined above.

The next $t$ lines each contain two integers $n, m$, where $n, m$ are as defined above.

Output

Output $t$ lines, each containing an integer representing the number of pairs $(i, j)$ such that $0 \le i \le n, 0 \le j \le \min(i, m)$ and $C_i^j$ is a multiple of $k$.

Examples

Input 1

1 2
3 3

Output 1

1

Note 1

Among all possible cases, only $C_2^1 = 2$ is a multiple of $2$.

Input 2

2 5
4 5
6 7

Output 2

0
7

Subtasks