Solve the programming task below in a Python markdown code block.
These days, chef is very much interested in Mathematics. He has started attending Recitations too! His hunger for problems is increasing day by day!
Today, chef was a given a crumpled maths problem, which he is stuck with . He needs your help to do it
Here's what his teacher said: "Find sum of all numbers till N, do not include numbers which are powers of K from K, K2, K3... which are less than or equal to N"
Easy, right? Can you solve it?

-----INPUT-----
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test contains two integers N and K, as per the above given problem specification.

-----OUTPUT-----
For each test case, output a single line printing the sum of the each test case, in format Case #T: S, where T is the Tth test case running and S is sum of corresponding test case.

-----CONSTRAINTS-----

10 < T < 50

10 < N < 104

0 < K < 100

-----EXAMPLE-----
Input:

2

10 3

20 2

Output:

Case #1: 43

Case #2: 180