We know, if we want to check whether a decimal number is divisible by 3, we need to find the sum of digits of that number. If the sum is divisible by 3, then the original number will also be divisible by 3. It took me a while to prove this. And then I realized this is true not only for 3 but for some other numbers as well. Sometimes not only for decimals but also for numbers in other bases as well. Can you find them? In particular, given a particular divisor D, you will have to find how many valid different bases B, less or equal to BMAX, are possible such that when we represent any number N in base B and the sum of digits of N is S, the following implication is true: N is divisible by D IF AND ONLY IF S is divisible by D. For example, if BMAX = 10, D = 3, the answer is 3. The bases are 4, 7 and 10. Input First line will contain T (T ≤ 10000), no of test cases. T lines will follow each with two integers BMAX (2 ≤ BMAX ≤ 1018) and D (1 ≤ D ≤ 1018). You can assume that base of a number system is positive and not less than 2. Output For each case print one line, ‘Case C: A’, where C is the case no and A is the required answer. Look at the output for sample input for details. Sample Input 2 10 3 20 3 Sample Output Case 1: 3 Case 2: 6