Counting Bits

For a positive integer N0, let N1 be the number of 1s in the binary representation of N0. For example, when N0 = 27 (binary 11011), N1 = 4.

For every i > 0, let Ni be the number of 1s in the binary representation of the previous term N(i-1). This sequence always converges to 1.

Given N0, let K be the smallest i for which Ni = 1. For example, when N0 = 31 the sequence gives N1 = 5, N2 = 2, N3 = 1, so K = 3.

Given a contiguous range and a number X, write a program that counts how many integers in the range, each taken as N0, have K equal to X.

The input consists of several test cases, one per line. Each line gives the range endpoints LO and HI and the value X (1 ≤ LO ≤ HI ≤ 10^18, 0 ≤ X ≤ 10). The last line contains three zeros.

For each test case, print the number of integers N0 in the range from LO to HI, inclusive, for which K equals X.