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

Difficulty: interview

Starter code:

Solutions:
testCases = int(input())
for c in range(testCases):
 n, k = list(map(int, input().split()))
 sum = 0
 i = 0
 power = 1
 while i <= n:
  if k**power == i:
   power += 1
  else:
   sum += i
  i +=1 
 answer = "Case #" + str(c + 1) + ": " + str(sum)
 print(answer)

for j in range(int(input())):
 n,k = list(map(int, input().split()))
 s = (n*(n+1))/2
 i = k
 while i<=n:
  s -= i
  i *= k
 print("Case #%d: %d" % (j+1, s))