Not One Bit More#1383
Start with a positive integer N_0. Let N_1 be the number of ones in the binary representation of N_0. For example, if N_0 = 27, then N_1 = 4.
In general, let N_i be the number of ones in the binary representation of N_{i-1}. This sequence always eventually reaches one.
For any starting number N_0, let K(N_0) be the minimal such that N_i = 1. For example, if N_0 = 31, then N_1 = 5, N_2 = 2, N_3 = 1, so K(31) = 3.
You are given a range of consecutive integers and a value . How many numbers in this range have K(...) = X?
The input contains several test cases. Each test case consists of three integers in a single line:
where and (1 \le LO \le HI \le 10^{18}) are the lower and upper bounds of the range of integers, and (0 \le X \le 10) is the target value for .
The input ends with a line containing three zeros.
For each test case, output a single integer in a separate line — the number of integers from to (inclusive), for which K(...) = X.
Example 1