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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


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))