提示: 欢迎访问OurACM平台。
Problem 2164 Jason's problem

Accept: 41    Submit: 79
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

计算n!表示成以b为底后的后缀零的个数非常容易。Jason遇到的问题刚好相反。Jason需要计算有共有多少个b,使得n!表示成以b为底后刚好有k个后缀零。

Input

第一行一个整数T(T <= 1000),表示有T组数据。

每组数据两行,第一行为n(1 <= n <= 10 ^ 15),第二行为k(1 <= k <= 10 ^ 15)。题目保证n/k < 500。

Output

对于每组数据,输出满足条件的b的个数。(输出 mod (10 ^ 9 + 7) 后的答案。)

Sample Input

3 10 2 10 4 10 8

Sample Output

24 4 1

Submit  Back  Status  Discuss