Arcane Numbers 2

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Vance and Shackler like playing games. After playing "arcane numbers", they find a new game “arcane numbers 2”. The game is also pretty simple. Vance first chooses 3 non-negative integers A, B and N, then he writes down B+A, B+A*2…B+A*N under base 2 and sends it to Shackler, after that Vance will ask him how many 1s are there in the sequence. However, the sequence is too long for Shackler and he turns to you for help. Given you A, B and N, please help Shackler to solve the problem.

Input

The first line contains a single integer T (T <= 20), the number of test cases. Then there are T lines with each case in a line. For each case, there are three integers A, B, N. 1<=A<=10000, 1<=B<=10^16, 1<=N<=10^12.

Output

For each case, you should print one line begin with “Case #”(quotations for explanation only) followed by the case number and a colon. After a single space, you should output the answer. (See the sample output for more details)

Sample Input

2 4 7 1 5 8 2

Sample Output

Case #1: 3 Case #2: 5

Hint

zhoujiaqi2010

Source

2012 Multi-University Training Contest 3

提交代码