#P1428. Christopher

    ID: 439 传统题 1000ms 512MiB 尝试: 112 已通过: 45 难度: 5 上传者: 标签>CF1800普及+/提高-Lucas 定理补集计数乘法原理进位制转换高精度除法高精度乘法高精度减法

Christopher

题目描述

给定 nn 和 pp 的值,希望你找出有多少个 mm,满足 (nm)\binom{n}{m} 是 pp 的倍数.

输入格式

第一行一个整数 TT 代表数据组数。

接下来 TT 行,每行两个数 n,pn,p 代表一组询问。

输出格式

对于每组询问,输出一个 [0,n][0,n] 里的整数表示答案。

3
5 5
3 2
4
0

数据规模与约定

对于 100%100\% 的数据,1≤T≤5001\leq T\leq 500,1≤n≤101001\leq n\leq 10^{100},pp 是质数。