时间限制：1秒　　内存限制：256M

---

【问题描述】

　　组合数表示的是从 \(n\) 个物品中选出 \(m\) 个物品的方案数。举个例子，从\(（1,2,3）\) 三个物品中选择两个物品可以有\(（1,2）,（1,3）,（2,3）\)这三种选择方法。根据组合数的定义，我们可以给出计算组合数的一般公式：

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

　　其中 \(n! = 1 × 2 × … × n\)。
　　小葱想知道如果给定 \(n,m\) 和 \(k\)，对于所有的 \(0 ≤ i ≤ n，0 ≤ j≤ min(i,m)\) 有多少对 \((i,j)\) 满足\(C_{i}^{j}\)是 \(k\) 的倍数。

【输入格式】

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

【输出格式】

　　\(t\) 行，每行一个整数代表答案。

【输入输出样例1】

　Input

1 2
3 3

　Output

1

【输入输出样例1说明】

　　在所有可能的情况中，只有 \(C_{2}^{1} = 2\) 是 \(2\) 的倍数。

【输入输出样例2】

　Input

2 5
4 5
6 7

　Output

0
7

【子任务】

【来源】

　　Mr.he