组合数表示的是从 n n n 个物品中选出 m m m 个物品的方案数。举个例子，从 (1,2,3) (1, 2, 3) (1,2,3) 三个物品中选择两个物品可以有 (1,2) (1, 2) (1,2)，(1,3) (1, 3) (1,3)，(2,3) (2, 3) (2,3) 这三种选择方法。
根据组合数的定义，我们可以给出计算组合数的一般公式：
Cnm=n!m!(n−m)! C_n ^ m = \frac{n!}{m!(n - m)!} Cnm=m!(n−m)!n!其中 n!=1×2×⋯×n n! = 1 \times 2 \times \cdots \times n n!=1×2×⋯×n。
小葱想知道如果给定 n n n，m m m 和 k k k，对于所有的 0≤i≤n 0 \leq i \leq n 0≤i≤n，0≤j≤min(i,m) 0 \leq j \leq \min(i, m) 0≤j≤min(i,m) 有多少对 (i,j) (i, j) (i,j) 满足是 k k k 的倍数。
第一行有两个整数 t t t，k k k，其中 t t t 代表该测试点总共有多少组测试数据，k k k 的意义见 「问题描述」。
接下来 t t t 行每行两个整数 n n n，m m m，其中 n n n，m m m 的意义见「问题描述」。
t t t 行，每行一个整数代表答案。
1 2 3 3
1
2 5 4 5 6 7
0 7
3≤n,m≤2000,2≤k≤21,1≤1≤10000 3 \leq n, m \leq 2000, 2 \leq k \leq 21, 1 \leq 1 \leq 10000 3≤n,m≤2000,2≤k≤21,1≤1≤10000