Problem #3185 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

双阶乘是一个数学概念，用 N!! 表示。当 $N$ 是自然数时， $N$ 的双阶乘表示不超过这个正整数 $N$ 且与 $N$ 有相同奇偶性的所有正整数乘积。

如，3!!=1×3=3，5!!=1×3×5=15，6!!=2×4×6=48，8!!=2×4×6×8=384。

请计算给定两个自然数 $N$ 和 $M$ ， $M$ 为 N!! 的分解质因数后的一个因子，求 N!! 分解质因数后因子 $M$ 的个数。

当输入 $N$ 为 $6$ ， $M$ 为 $2$ 时， $6!! = 2 \times 4 \times 6 = 2^{4} \times 3$ ，输出因子 $2$ 的个数为 $4$ 。

第 $1$ 行：一个整数 T（1≤T≤10）为问题数。

第 $2$ ~ $T + 1$ 行：每个问题占一行，每行输入两个自然数：N（1<N≤10000）和一个因子 $M$ （数据保证 $M$ 是 $N!!$ 的质因子）。

对于每个问题，输出一行问题的编号（ $0$ 开始编号，格式：case #0: 等）。然后对应每个问题在一行中输出N!!质因数分解后因子M的个数。

Input

Output

case #0:
7
case #1:
2
case #2:
251

610 人解决，633 人已尝试。

769 份提交通过，共有 1258 份提交。

0.5 EMB 奖励。

创建: 7 年，11 月前.

修改: 6 年，7 月前.

最后提交: 6 天，1 小时前.

来源: N/A

implementation

3185. 双阶乘的质因数个数