组合数 (n,m)表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。特别地，定义 $0!=1$。

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0\le i\le n,0\le j\le \min \left(i,m\right)$ 有多少对 $(i,j)$ 满足 k| 组合数(i,j)。

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

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

• 对于全部的测试点，保证 0<=n,m<=2*10^3，1<=t<=10^4。