11389: Rightmost non-zero Digit in N!

Memory Limit:128 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

The expression N!, read as "N factorial," denotes the product of the first N positive integers, where N is nonnegative. So, for example

N N!

0 1

1 1

2 2

3 6

4 24

5 120

10 3628800

For this problem, you are to write a program that can compute the rightmost non-zero digit of the factorial for N in base B.


Input

In the first line there is an integer T (T <= 100), indicates the number of test cases.

In each case, there is a single line with integers N and B

(0<=N<=10^7, 2<=B<=10^4).


Output

For each case, the output format is “Case #c: ans”. 

c is the case number start from 1.

ans is the answer of this problem. The ans is in base 10.

See the sample for more details.


Sample Input Copy

2
13 3
11 11

Sample Output Copy

Case #1: 2
Case #2: 10

HINT

Case #1:

13*12*11*10*9*8*7*6*5*4*3*2*1=6227020800 base 10, which in base 3 is
121001222020102200000, so the right-most non-zero digit is 2.