Not One Bit More
Start with an integer, N_0, which is greater than 0. Let N_1 be the number of ones in the binary representation of N_0. So, if N_0 = 27, N_1 = 4.
In general, let N_i be the number of ones in the binary representation of N_{i-1}. This sequence will always converge to one.
For any starting number, N_0, let K(N_0) be the minimum i such that N_i is one. For example, if N_0 = 31, then N_0 = 5, N_{1 }= 5, N_2 = 2, N_3 = 1, so K(31) = 3.
Given a range of consecutive numbers, and a value X, how many numbers in the range have a K(...) value equal to X?
Input
There will be several test cases in the data file. Each test case will consist of three integers on a single line:
LO HI X
where LO and HI (1 ≤ LO ≤ HI ≤ 10^18) are the lower and upper limits of a range of integers, and X (0 ≤ X ≤ 10) is the target value for K(...).
The data file will end with a line with three 0s.
Output
For each test case, output a line with a single integer, representing the number of integers in the range from LO to HI (inclusive) which have a K(...) value equal to X in the input.