4718번 - Not One Bit More 다국어

Start with an integer, N₀, which is greater than 0. Let N₁ be the number of ones in the binary representation of N₀. So, if N₀ = 27, N₁ = 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, N0, let K(N0) be the minimum i such that Ni is one. For example, if N₀ =31, then N₁ =5, N₂ =2, N₃ =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?

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¹⁸) 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.

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.