UOJ Logo LFYZ Online Judge

LFYZOJ

#37. 【NOIP2016 提高组】组合数问题

统计

问题描述

组合数 $C_n^m$ 表示的是从 $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$ 行,每行一个整数代表答案。

样例一

input

1 2
3 3

output

1

explanation

在所有可能的情况中,只有 $C_2^1 = 2$ 是 $2$ 的倍数。

样例二

input

2 5
4 5
6 7

output

0
7

数据范围与约定

chart

时间限制: $1\mathrm{s}$

内存限制: $512\mathrm{MB}$