Background

NOIP2016 提高组 D2T1

Description

组合数$\binom{n}{m}$表示的是从n个物品中选出m个物品的方案数。举个例子，从(1,2,3)三个物品中选择两个物品可以有(1,2)、(1,3)、(2,3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数$\binom{n}{m}$的一般公式： $\binom{n}{m}=\frac{n!}{m!(n-m)!}$ 其中 $n!=1×2×⋯×n$；特别地，定义0! = 1。 小葱想知道如果给定n、m和k，对于所有的0 ≤ i ≤ n, 0 ≤ j ≤ min(i, m)有多少对(i, j)满足$k|\binom{i}{j}$。

Format

Input

第一行有两个整数t和k，其中t代表该测试点总共有多少组测试数据，k的意义见问题描述。 接下来t行，每行两个整数n和m，其中n和m的意义见问题描述。

Output

共t行，每行一个整数代表所有的$0\leq i\leq n$, $0\leq j\leq \min \left ( i, m \right)$中有多少对(i, j)满足$k|\binom{i}{j}$。

Samples

2 5
4 5
6 7

0
7

Limitation

1s, 1024KiB for each test case.