Problem 3

2012 ACU Programming Contest Series

Problem 3: Recurse

The Amalagated Consortium Union (ACU) recently discovered an interesting recursive function, fk(i, j), deserving more investigation. The function f relies on the set generating function g (see Problem 2).

fk(i, j) = max( fk(i, j-1), fk(e, j), fk(e, j-1) ), where e ∈ g(i, j), if j > 0
fk(i, j) = number of 1 bits in the binary representation of i + k, if j = 0

g(i, j) = { nj + i mod j + 1, nj + i mod j + 2, ..., nj + j - 1 | n=0, 1, ..., i / j }

Write a program to evaluate fk(i, j).

Input

The first line consists of a single integer, the number of data sets to process.

Each data set consists of a single line consisting of three non-negative integers, i, j, and k, all less than 100, separated by single spaces.

    

Output

Each data set should produce one line of output, the result of evaluating fk(i, j).

Sample input: 

4
7 0 0
4 1 3
1 3 0
2 3 1
     Sample output: 
3
7
16
15