7748: G_4

FQ是个喜欢数学的孩子。有一天，FQ发明了一个函数FQ(n,p)。FQ(n,p)的值描述了n!最多可以被p的多少次幂整除，其中p为一个素数。

举例来说，对于FQ(8,3)，我们要考查8! = 8×7×6×5×4×3×2×1 = 40320。很容易发现，它可以被3²整除，但是不能被3³整除。所以FQ(8,3) = 2，表示8!最多可以被3²整除。

对FQ(k,p)可以严格的定义：k!可被p^FQ(k,p)整除，但是不能被p^FQ(k,p)+1整除。

ZQ对FQ的发现很感兴趣，但是他对FQ在这个函数的讨论中仅使用十进制表示不满。ZQ于是定义了ZQ(n,p)。其中n是个p进制正整数，并且 ZQ(n,p) = FQ(n₁₀,p)。其中n₁₀表示n转换成十进制之后对应的数字。

本题的任务就是求出ZQ(n,p)的值。注意：请将答案表示为十进制数。

输入数据有多组，输入文件的第一行是测试数据的数目T(T≤50)。

每组测试数据占一行，是用空格分开的两个正两个整数n，p。

数据保证：(1) p≤16，并且p是素数。 (2) n是一个p进制正整数，长度不超过10⁵。(3)在高于十进制的进制中，使用A表示10，B表示11，C表示12，D表示13，E表示14，F表示15。

对于每组测试用例，输出一行，包含一个整数表示你的答案。请将答案表示为十进制数。另外，由于答案可能太大，你只需要输出答案模1000000007的余数。

2
11 2
1A1 11

1
22