Christopher

时间限制:10s      空间限制:162MB

题目描述

给定N和P的值,希望你找出有多少个M,满足C(N,M)是P的倍数.


输入格式

第一行给出数字X,代表有多少组数据. 下面每一行两个数字,代表N和P


输出格式

输出包括X行,每行一个数字,代表在0到N之间满足条件的数字M有多少个.


样例输入

3
5 5
3 2

样例输出

4
0

提示

1<=X<=500 N<=10^100 P为质数,且小于10^7


题目来源

没有写明来源