4321：Arcane Numbers 2

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.

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.

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)