题目描述
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
输入格式
见题面
输出格式
见题面