#2361. 「NOIP2016」组合数问题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1, 2, 3) 三个物品中选择两个物品可以有 (1, 2) (1, 3) (2, 3) 这三种选择方法。

根据组合数的定义,我们可以给出计算组合数的一般公式:

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

其中 n! = 1 \times 2 \times \cdots \times n

小葱想知道如果给定 n m k ,对于所有的 0 \leq i \leq n 0 \leq j \leq \min(i, m) 有多少对 (i, j) 满足 C_i ^ j k 的倍数。

输入格式

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

接下来 t 行每行两个整数 n m ,其中 n m 的意义见「题目描述」。

输出格式

t 行,每行一个整数代表所有的 0 \leq i \leq n 0 \leq j \leq \min(i, m) 有多少对 (i, j) 满足 C_i ^ j k 的倍数。

样例

样例输入 1

1 2
3 3

样例输出 1

1

样例输入 2

2 5
4 5
6 7

样例输出 2

0
7

数据范围与提示

3 \leq n, m \leq 2000, 2 \leq k \leq 21, 1 \leq t \leq 10000