题目描述

给定 $n$ 和 $p$ 的值，希望你找出有多少个 $m$，满足 $\binom{n}{m}$ 是 $p$ 的倍数.

输入格式

第一行一个整数 $T$ 代表数据组数。

接下来 $T$ 行，每行两个数 $n,p$ 代表一组询问。

输出格式

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

3
5 5
3 2

4
0

数据规模与约定

对于 $100\%$ 的数据，$1\leq T\leq 500$，$1\leq n\leq 10^{100}$，$p$ 是质数。