3185. 双阶乘的质因数个数

单点时限: 2.0 sec

内存限制: 256 MB

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

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

请计算给定两个自然数 N!! 的分解质因数后的一个因子,求 N!! 分解质因数后因子 的个数。

当输入 时,,输出因子 的个数为

输入格式

行:一个整数 T(1≤T≤10)为问题数。

~ 行:每个问题占一行,每行输入两个自然数:N(1<N≤10000)和一个因子(数据保证的质因子)。

输出格式

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

样例

Input
3
8 2
15 5
999 3
Output
case #0:
7
case #1:
2
case #2:
251

383 人解决,396 人已尝试。

493 份提交通过,共有 784 份提交。

0.8 EMB 奖励。

创建: 2 年,5 月前.

修改: 1 年,1 月前.

最后提交: 2 月前.

来源: N/A

题目标签